[Baekjoon Online Judge] 2178번: 미로 탐색

2178번: 미로 탐색

[그래프 탐색] DFS와 BFS

N x M 크기의 배열로 표현된 미로가 있다.

요구사항

 1. 1은 이동할 수 있는 칸을 나타낸다. 0은 이동할 수 없는 칸을 나타낸다.

 2. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하라.

 3. 칸을 셀 때 시작 위치와 도착 위치를 포함한다.

 

입력 

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

출력

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

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon2178 {

    static int[][] graph;
    static int[][] visited;
    static int n, m;

    static class Location {
        int x, y;
        public Location(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void bfs(int startX, int startY) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(new Location(startX, startY));

        System.out.println("add (" + startX+ ", " + startY + ")");
        System.out.print("[");
        for (Location value : queue) {
            System.out.print("(" + value.x + ", " + value.x + ")");
        }
        System.out.print("]");
        System.out.println();

        /**                     상 x - 1, y
         *  좌 x, y - 1             x, y             우 x, y + 1
         *                      하 x + 1, y
         */
        //             상, 하, 좌, 우
        int[] xMove = {-1, 1, 0, 0};
        int[] yMove = {0, 0, -1, 1};

        visited[startX][startY] = 1;

        while (!queue.isEmpty()) {
            Location location = queue.poll();
            int row = location.x;
            int col = location.y;
            System.out.println("poll (" + row + ", " + col + ")");
            System.out.print("[");
            for (Location value : queue) {
                System.out.print("(" + value.x + ", " + value.y + ")");
            }
            System.out.print("]");
            System.out.println();

            for (int i = 0; i < 4; i++) { // 상하좌우 4방향 탐색
                int x = row + xMove[i];
                int y = col + yMove[i];

                if (isLocation(x, y)) {
                    queue.add(new Location(x, y));
                    System.out.println("add (" + x + ", " + y + ")");
                    System.out.print("[");
                    for (Location value : queue) {
                        System.out.print("(" + value.x + ", " + value.y + ") - ");
                    }
                    System.out.print("]");
                    System.out.println();
                    visited[x][y] = visited[row][col] + 1;
                }
            }
        }
    }

    public static boolean isLocation(int x, int y){
        if(x < 1 || x > n || y < 1 || y > m) return false;
        if(visited[x][y] != 0 || graph[x][y] == 0) return false;
        return true;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = bufferedReader.readLine().split(" ");

        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        graph = new int[n + 1][m + 1];
        visited = new int[n + 1][m + 1];

        for(int i = 1; i <= n; i++){
            String row = bufferedReader.readLine();
            for(int j = 1; j <= m; j++) {
                graph[i][j] = row.charAt(j - 1) - '0';
            }
        }

        bfs(1, 1);

        bufferedWriter.write(String.valueOf(visited[n][m]));

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

4 6
101111
101010
101011
111011
add (1, 1)
[(1, 1)]
poll (1, 1)
[]
add (2, 1)
[(2, 1) - ]
poll (2, 1)
[]
add (3, 1)
[(3, 1) - ]
poll (3, 1)
[]
add (4, 1)
[(4, 1) - ]
poll (4, 1)
[]
add (4, 2)
[(4, 2) - ]
poll (4, 2)
[]
add (4, 3)
[(4, 3) - ]
poll (4, 3)
[]
add (3, 3)
[(3, 3) - ]
poll (3, 3)
[]
add (2, 3)
[(2, 3) - ]
poll (2, 3)
[]
add (1, 3)
[(1, 3) - ]
poll (1, 3)
[]
add (1, 4)
[(1, 4) - ]
poll (1, 4)
[]
add (1, 5)
[(1, 5) - ]
poll (1, 5)
[]
add (2, 5)
[(2, 5) - ]
add (1, 6)
[(2, 5) - (1, 6) - ]
poll (2, 5)
[(1, 6)]
add (3, 5)
[(1, 6) - (3, 5) - ]
poll (1, 6)
[(3, 5)]
poll (3, 5)
[]
add (4, 5)
[(4, 5) - ]
add (3, 6)
[(4, 5) - (3, 6) - ]
poll (4, 5)
[(3, 6)]
add (4, 6)
[(3, 6) - (4, 6) - ]
poll (3, 6)
[(4, 6)]
poll (4, 6)
[]
15

 

 BFS를 활용하여 문제를 해결 하였다. 미로의 좌표를 queue에 삽입하고, 해당 좌표의 값을 이동하여 맞는 좌표인지 확인하고 맞다면 queue에 삽입한다. 해당 좌표로 방문한 기록이 visited 이차 배열에 차곡차곡 쌓이게 되고 N, M값을 출력하면 최소값을 구할 수 있다. 위의 출력은 queue가 poll하고 add 하는 과정을 디버깅 한 것이다.