[BFS/자바] 백준 2178. 미로 탐색

2178번: 미로 탐색

최단 기간의 경로를 구하고 있으므로 BFS가 적절한 선택일 것이다.

public class B2178 {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean [][] visited;
    static int[][] arr;
    static int n, m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(line.substring(j, j + 1));
            }
        }
        
        BFS(0, 0);
        bw.write(Integer.toString(arr[n - 1][m - 1]));
        bw.flush();
        br.close();
        bw.close();
    }

    private static void BFS(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int now[] = queue.poll();
            visited[i][j] = true;
            for (int k = 0; k < 4; k++) { // 상하좌우 탐색
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if (x >= 0 && y >= 0 && x < n && y < m) { // 배열을 넘어가면 안되고
                    if (arr[x][y] != 0 && !visited[x][y]) { // 0이여서 갈 수 없거나, 방문한 곳이면 안됨
                        // 이제 갈 수 있는 곳이다.
                        visited[x][y] = true;
                        arr[x][y] = arr[now[0]][now[1]] + 1; // 핵심
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
    }

}