[SWEA]#1226 [S/W 문제해결 기본] 7일차 - 미로1

문제

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.

가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.

주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

아래의 예시에서는 도달 가능하다.

아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).

예제 입력 1

1
1111111111111111
1210000000100011
1010101110101111
1000100010100011
1111111010101011
1000000010101011
1011111110111011
1010000010001011
1010101111101011
1010100010001011
1010111010111011
1010001000100011
1011101111101011
1000100000001311
1111111111111111
1111111111111111
2
1111111111111111
1200000010000011
1011111011111011
1000001010000011
1110101010111011
1010101010100011
1011111010111111
1000001010000011
1011101011111011
1010101010000011
1010101010111111
1010100000130011
1010111111111011
1000000000000011
1111111111111111
1111111111111111
...

예제 출력 1

#1 1
#2 1
...

풀이

이 문제는 bfs(너비 우선 탐색) 알고리즘을 이용해서 푸는 가장 일반적인 문제이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;

class Solution
{
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = 10;

		for(int test_case = 1; test_case <= T; test_case++)
		{
            br.readLine();
            int[][] map = new int[16][16];
            int startX = 0;
            int startY = 0;
            
            for(int i=0; i<16; i++) {
                String input = br.readLine();
                
                for(int j=0; j<16; j++) {
                    map[i][j] = input.charAt(j) - '0';
                    
                    if(map[i][j]==2) {
                        startX = i;
                        startY = j;
                    }
                }
            }
            
            int ans = bfs(map, startX, startY);
            
            System.out.println("#"+test_case+" "+ans);
		}
	}
    
    public static int bfs(int[][] map, int x, int y) {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[16][16];
        visited[x][y] = true;
        queue.add(new Pair(x, y));
        
        while(!queue.isEmpty()) {
            Pair temp = queue.poll();
            
            for(int i=0; i<4; i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];
                
                if(nx<0 || nx>=16 || ny<0 || ny>=16 || visited[nx][ny]) continue;
                
                if(map[nx][ny]==0) {
                    visited[nx][ny] = true;
                	queue.add(new Pair(nx, ny));
                }
                
                else if(map[nx][ny]==3)
                    return 1;
            }
        }
        
        return 0;
    }
    
    public static class Pair {
        int x;
        int y;
        
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}