[필수 문제] 미로 찾기

1. 문제

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다.

---

입력

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

출력

(N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다.

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 0 1 0
0 1 1 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 1 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0

예제 출력

22

 

 

 

2. 풀이

이 문제는 BFS를 이용하여 풀어야한다. 배열을 돌면서 0인 곳을 만나면, 그 곳을 기준으로 배열의 범위를 벗어나지 않는 상하좌우를 순회하면서 방문하지 않고, 0인 곳이라면 (기준이 되는 곳 + 1)하여 값을 채워넣어주어 해결한다.

9	10	11	12	13	14	1	1	23	22(끝)
8	1	1	1	12	13	1	15	1	21
7	1	1	1	11	12	1	14	1	20
6	7	8	9	10	11	12	13	1	19
5	6	1	1	1	1	13	14	1	18
4	5	6	7	8	9	1	1	16	17
3	4	1	1	1	10	1	1	15	16
2	3	1	1	1	11	12	13	14	15
1	2	3	4	5	1	1	1	15	16
0(시작)	1	2	3	4	5	6	1	16	17

import java.io.*;
import java.util.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int m;

    private static int[][] arr;
    private static boolean[][] isVisited;

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][m];
        isVisited = new boolean[n][m];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs(n-1, 0);

        bw.write(arr[0][m-1] + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static void bfs(int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {i, j});
        isVisited[i][j] = true;

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

            for(int k = 0; k < 4; k++) {
                int y = w[0] + dy[k];
                int x = w[1] + dx[k];

                if(y >= 0 && y < n && x >=0 && x < m) {
                    if(arr[y][x] == 0 && !isVisited[y][x]) {
                        queue.add(new int[] {y, x});
                        isVisited[y][x] = true;
                        arr[y][x] = arr[w[0]][w[1]] + 1;
                    }
                }
            }
        }
    }
}