BOJ 2178. 미로탐색

BOJ 2178. 미로 탐색

풀이

0과 1로 이루어진 2차원 배열이 주어지고, 1은 이동할 수 있는경로 0은이동할 수 없는 경로이다.
시작점에서 상하좌우를 탐색하며 값이 1인 탐색할 수 있는 길을통해 (N,M)으로 이동한다.
이동하면서 거리를 1씩 증가하며 dist에 저장한다. 최종 도착점인 (N,M)에 도달하였을 때 거리를 출력한다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[][] board = new int[n][m];
        int[][] dist = new int[n][m];
        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = Character.getNumericValue(s.charAt(j));
            }
        }

        Queue<int[]> queue = new LinkedList<>();

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};

        dist[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 1) {
                    queue.offer(new int[]{i, j});

                    while (!queue.isEmpty()) {
                        int[] p = queue.poll();

                        for (int k = 0; k < 4; k++) {
                            int x = p[0] + dx[k];
                            int y = p[1] + dy[k];
                            if (x < 0 || x >= n || y < 0 || y >= m) continue;
                            if (board[x][y] != 1 || dist[x][y] > 0) continue;
                            queue.offer(new int[]{x, y});
                            dist[x][y] = dist[p[0]][p[1]] + 1;
                        }
                    }
                }
            }
        }

        System.out.println(dist[n - 1][m - 1]);
    }
}