[백준] 2178번 : 미로 탐색

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

# 출력

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

# 예제 입력 1

4 6

101111

101010

101011

111011

# 예제 출력 1

15

# 예제 입력 2

4 6

110110

110110

111111

111101

# 예제 출력 2

9

# 예제 입력 3

2 25

1011101110111011101110111

1110111011101110111011101

# 예제 출력 3

38

 

# 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

두 정점간 최단 거리를 구할 때는 BFS를 사용한다. 생각하기 나름 이지만 동적 프로그래밍(?) 도 약간 가미 되었다고 생각한다. 주어진 테이블 위 (1, 1)에서 (N, M)으로 가기 위해 BFS를 사용할텐데, BFS는 갈 수 있는 모든 좌표를 방문하는 알고리즘이다. 모든 좌표를 방문하는 방법은 결코 최단 거리가 아니다. 그렇다면 이건 어떠한가? 모든 좌표가 값을 가지는 것 이다. 그 값은 (1, 1)에서 (y, x)까지 거친 좌표 수가 되면 좋을 것 같다. 그럼 최종 목적지인 (N, M)의 값이 최단 거리가 될 수 있을테니 말이다. 글보다는 표를 보는 것이 더 이해하기 쉬울 것 같다.

 

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

이와 같은 표가 있을 때, (1, 1)에서 (4, 4) 까지의 최단 경로는 7이다. 표의 값을 바꿔가면서 보도록 하자.

 

# 1

(1,1)에서 시작이므로 해당 정점은 방문했다. 방문했다는 표시로 거쳐간 정점의 개수 1을 표시해야하는데, 1로 표기하면 문제에서 주어진 입력과 혼동되므로 2로 표기하도록 하고, 마지막 결과를 출력할 때 -1 해주는 것으로 한다.

2	0	1	1
1	0	1	0
1	1	1	1
0	1	0	1

 

# 2

(1, 1)에서 갈 수 있는 곳은 (2, 1)이다. (1, 1)에서 (2, 1)사이엔 정점이 2개 있으므로 값은 ((1,1)의 값 + 1) = 3이 될 것이다.

2	0	1	1
3	0	1	0
1	1	1	1
0	1	0	1

 

# 3

(2, 1)에서 갈 수 잇는 곳은 (3, 1)이다. (3, 1)의 값을 ((2,1)의 값) + 1) = 4로 변경한다.

2	0	1	1
3	0	1	0
4	1	1	1
0	1	0	1

 

# 4

(3, 1)에서 갈 수 있는 곳은 (3, 2) 이고 이 곳의 값을 ( (3,1)의 값 ) + 1) = 5로 변경한다.

2	0	1	1
3	0	1	0
4	5	1	1
0	1	0	1

 

# 5

(3, 2)에서 갈 수 있는 곳은 (4, 2)와 (3, 3)이다. 이 정점들의 값을 ( (3,2)의 값) + 1) = 6으로 변경한다.

2	0	1	1
3	0	1	0
4	5	6	1
0	6	0	1

 

# 6

(4, 2)에서는 더 이상 갈 곳이 없다.

(3, 3)에서 갈 수 있는 곳은 (3, 4)와 (2, 3)이므로 이 정점들의 값을 ( (3,3)의 값) + 1)=7로 변경한다.

2	0	1	1
3	0	7	0
4	5	6	7
0	6	0	1

 

# 7

(3, 4)에서 갈 수 있는 곳은 우리가 궁극적으로 원하는 정점인 목표 정점이다. (4, 4)정점의 값을 8로 변경한다. (2, 3)에서 갈 수 있는 정점들의 과정은 생략)

2	0	1	1
3	0	7	0
4	5	6	7
0	6	0	8

 

마지막에 결과 출력 과정에서 반드시 -1을 해주어야 원하는 결과 값을 출력할 수 있다.

# Whole Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
    
    static int[] arrY = {1, 0, -1, 0};
    static int[] arrX = {0, 1, 0, -1};
    static Queue<Point> Q = new LinkedList<>();
    static short[][] table;

    static void BFS(int rows, int cols){

        table[1][1] = 2; //(1,1) 방문
        Q.add(new Point(1, 1));

        while(!Q.isEmpty()){
            Point p = Q.poll(); //Dequeue
            int y = p.y;
            int x = p.x;

            for(int i=0; i<4; i++)
                if(table[y+arrY[i]][x+arrX[i]] == 1){
                	//(y,x)에서 방문 가능한 정점 방문
                    table[y+arrY[i]][x+arrX[i]] = (short) (table[y][x] + 1);
                    Q.add(new Point(y+arrY[i], x+arrX[i])); //Enqueue
                }
        }
        if(table[rows][cols] != 1) System.out.print(table[rows][cols]-1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int rows = sc.nextInt();
        int cols = sc.nextInt();

        table = new short[rows+2][cols+2];

        for(int i=1; i<=rows; i++){
            String[] str = sc.next().split("");
            for(int j=1; j<=cols; j++)
                table[i][j] = Short.parseShort(str[j-1]);
        }
        BFS(rows, cols);
    }
}