2178 : 미로 탐색

출처 : https://www.acmicpc.net/problem/2178

---

문제

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

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

입력

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

출력

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

---

접근

• BFS의 기초가 되는 문제이다.
• 이 문제에서 사용된 BFS 함수와 그 안의 while문은 앞으로의 BFS 응용 문제에서도 사용될 예정이기 때문에, 본인은 먼저 함수를 아예 외우고, 그 다음 문제를 반복적으로 풀면서 이해하는 방식을 택했다.  
• 출발점이 (1,1)으로 고정되어 있기 때문에 좀 더 수월하게 풀 수 있었다.
• index가 0이 아닌 1부터 시작한다는 점을 주의한다.
• [입력] 부분을 보면, 각각의 수들은 '붙어서' 입력된다고 한다. 아래의 코드에서는 split함수를 이용하여 구별하였지만, Bufferedreader와 StringTokenizer함수를 이용하면 훨씬 편할 것이라고 예상한다. 

(이 문제는 알고리즘 공부 초기에 풀었기 때문에 Scanner함수를 사용하였다. 이 후의 글에서는 점차 Bufferedreader함수가 사용되는걸 볼 수 있을 것이다. )

 

---

코드

import java.util.*;
 
public class Main {
 
    static int N;
    static int M;
    static int[][] map; // 미로
    static boolean[][] visit; // 방문 여부 표시
    static int[] dx = { -1, 0, 1, 0 };    // 상,하,좌,우 를 방문하기 위해 
    static int[] dy = { 0, -1, 0, 1 };
 
    public static void BFS(int X, int Y) {
        Queue<Integer> qx = new LinkedList<Integer>();
        Queue<Integer> qy = new LinkedList<Integer>();
 
        qx.add(X);
        qy.add(Y);
 
        while (!qx.isEmpty() && !qy.isEmpty()) {
            X = qx.poll();
            Y = qy.poll();
            visit[X][Y] = true; // true는 '방문함'을 의미
 
            for (int i = 0; i < 4; i++) {
                int nextX = X + dx[i];
                int nextY = Y + dy[i];
 
                if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M) { // 범위 내에 있다면
                    if (map[nextX][nextY] == 1 && visit[nextX][nextY] == false) { // 방문하지 않았다면
                        qx.add(nextX);
                        qy.add(nextY);
                        visit[nextX][nextY] = true;
                        map[nextX][nextY] = map[X][Y] + 1; // 미로의 값은 이동 횟수로 변경
                    }
                }
            }
        }
    }
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
 
        N = sc.nextInt(); // 행
        M = sc.nextInt(); // 열
 
        map = new int[N][M];
        visit = new boolean[N][M];
 
        for (int i = 0; i < N; i++) {
            String[] s = sc.next().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }
 
        BFS(0, 0);
        System.out.println(map[N - 1][M - 1]);
 
        sc.close();
 
    }
 
}