[백준/2178] - 미로 탐색(JAVA)

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

---

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

---

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

풀이

---

public class Main {
    static int N, M;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            String row = br.readLine();
            for (int j=0; j<M; j++){
                field[i][j] = row.charAt(j)-48;
            }
        }
        BFS(0,0);
        System.out.println(field[N-1][M-1]);
    }
    static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()){
            int[] now = queue.poll();
            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >=0 && ny >= 0 && nx < N && ny < M){
                    if (!visited[nx][ny] && field[nx][ny] != 0){
                        visited[nx][ny] = true;
                        field[nx][ny] = field[now[0]][now[1]] + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

해설

---

전형적인 BFS문제다. 완전탐색하며 몇번째 뎁스에서 원하는 값을 찾을 수 있는지를 확인하는 문제다.

최단거리를 구하는 것이 왜 BFS가 유리한지, BFS가 왜 '너비 우선 탐색'인지를 알 수 있는 좋은 문제다.

DFS는 일단 가면서 탐색하여 시간초과를 일으키지만 BFS는 해당 깊이에서 갈 수 있는 노드를 탐색하고 가기 때문에 최단거리 문제 풀이에 조금 더 용이하다.

먼저 DFS의 진행 상황을 분석하고 풀이로 넘어간다.

4 6
110110
110110
111111
111101

 

위의 예제를 depth를 따라가보자.

모든 '뎁스를 탐색하는 과정'에서 탐색했으면 좌표 안에 최단거리를 집어넣어줘야 한다.

 

depth1

(0,0)을 확인하고 방문 배열을 체크한 다음, 상하좌우를 확인하면서 막혀있지 않고, 숫자가 1이라면 그 좌표를 새로 큐에 추가한다. 새로 추가한 좌표는 방문 배열에 미리 체크해놓는다.

현재 큐 = [[1,0], [0,1]]

depth 2

• (1,0)을 확인하고, 상하좌우를 확인하고 조건에 맞는 (1,1)좌표를 큐에 추가하고 방문 배열에 (1,1)을 체크한다.
• (0,1)을 확인하고, 상하좌우를 확인하고 조건에 맞는 (0,2)좌표를 큐에 추가한다. (1,1)은 이미 방문 배열에 있으므로 추가하지 않는다.

현재 큐 = [[1,1], [2,1]]

depth 3

• (1,1)을 확인하고, 상하좌우를 확인한 뒤 조건에 맞는 (2,1)좌표를 큐에 추가하고 방문 배열을 체크한다.
• (0,2)을 확인하고, 상화좌우를 확인한 뒤 조건에 맞는 (0,3)좌표를 큐에 추가하고 방문 배열을 체크한다.

현재 큐 = [[2,1], [0,3]]

 

이런식으로 depth를 하나씩 늘려서 진행한다.

결국 마지막에 배열은 다음과 같이 변한다.

1	2	0	8	9	0
2	3	0	7	8	0
3	4	5	6	7	8
4	5	6	7	0	9

각 배열의 값은, 이 배열까지 오기 위한 depth의 최소값을 띄게 된다.

 

이제, 코드를 살펴보자.

    static int N, M;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

특이사항 없이 가로, 세로를 받을 N, M과 배열을 받고 뎁스를 기록할 field, 방문 기록용 visited 배열과 델타 배열을 선언한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            String row = br.readLine();
            for (int j=0; j<M; j++){
                field[i][j] = row.charAt(j)-48;
            }
        }
        BFS(0,0);
        System.out.println(field[N-1][M-1]);
    }

field배열을 채우고, (0,0)에서 BFS를 시작하고 맨 마지막에 도착지의 depth를 출력하면 된다.

static void BFS(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()){
            int[] now = queue.poll();
            for (int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >=0 && ny >= 0 && nx < N && ny < M){
                    if (!visited[nx][ny] && field[nx][ny] != 0){
                        visited[nx][ny] = true;
                        field[nx][ny] = field[now[0]][now[1]] + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }

가장 중요한 BFS 함수다

큐를 선언하는것부터 시작하는데, 큐에 집어넣을 노드는 int형 배열이 되어야 한다.

방문 배열에 추가해주고, 큐가 빌 때까지 계속 뽑아낸다.

델타 배열을 방문하면서 방문하지 않았고 배열값이 0이 아닌 노드에 한해서

방문 배열을 체크해주고, 지나온 값에 이전까지의 뎁스를 기록한다.

마지막으로 새로운 좌표를 다시 큐에 추가해주고 계속 while문을 돌리면 된다.

 

어렵지는 않았으나, 처음 BFS 문제를 풀 때에는 조금 어려운 감이 있다.

그러나 BFS의 원리를 알고 원리대로 프로그래밍을 풀어간다면 코드 자체는 어렵지 않다.