Baekjoon Online Judge _ 02178 _ 미로 탐색

[ Baekjoon Online Judge _ 02178 _ 미로 탐색 ]

문제

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

출력

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

예제 입력

4 6
101111
101010
101011
111011

예제 출력

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

풀이

BFS를 사용해서 풀었다.

그래프 탐색방법으로 DFS와 BFS를 배웠찌만 길찾기 알고리즘으로 적용하는 것은 처음해봤다.

그래서 여러 코드를 참고해 풀면서 BFS를 이해할 수 있었다!

일단 BFS는 큐를 사용한다. (DFS는 스택)

큐에는 시작점 하나가 들어있는 상태.

큐에서 원소 하나를 뺀다. (cursor)

그 점(cursor)과 연결된 점들 중 방문되지 않은 점들을 모두 큐에 넣고 큐에 넣는 점은 방문했음을 표시해준다.

방문할 때마다 1씩 늘려가며 누적해서 해당 점까지의 길이를 저장했다.

위 과정을 큐가 빌 때까지 반복해주면 된다.

처음엔 BFS개념이 이해가 안갔다.

그러다 가장 쉽게 이해됐던 설명은

여러 갈래의 길이 있을 때 동시에 한칸씩 나아간다는 거다.

예를들어 목적지까지 다다르는 길이가 10, 8, 9 인 각각의 길이 있을 때

BFS는 이 길들을 한칸씩 동시에 나아간다.

8번째 나아갔을 때 길이가 8인 길은 목적지에 도착할 것이고 목적지는 방문된 것으로 표시된다. (다시 방문되지 않는다는 뜻)

결국 모든 길을 끝까지 가도 목적지는 길이가 8인 상태를 유지할 것이고 그것이 목적지까지의 최단 거리가 된다!

코드

import java.util.ArrayDeque;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        
        class Point{
            int x, y;
            
            Point(int x, int y){
                this.x = x;
                this.y = y;
            }
        }
        
        Scanner sc = new Scanner(System.in);
        
        int N,M;
        ArrayDeque<Point> queue = new ArrayDeque<Point>(); //큐
        String temp;   //입력받기위한 배열
        int[][] maze;    //미로
        int[][] visit;   //방문순서, 방문여부표시
        
        N = sc.nextInt();
        M = sc.nextInt();
        
        maze = new int[N][M];
        visit = new int[N][M];
        
        for(int i = 0; i < N; i++){
            temp = sc.next();
            for(int j = 0; j < M; j++){
                maze[i][j] = temp.charAt(j) - '0';
            }
        }
        
        //시작점초기화
        Point start = new Point(0,0);
        queue.offer(start);
        visit[start.x][start.y] = 1;
        
        //BFS
        while(!queue.isEmpty()){
            Point cursor = queue.poll(); //큐에서꺼냄
            
            //미로범위 안 & 길 있음 & 방문 전
            //위
            if(cursor.x - 1 >= 0 && maze[cursor.x - 1][cursor.y] == 1 && visit[cursor.x - 1][cursor.y] ==0){
                Point next = new Point(cursor.x - 1, cursor.y);
                queue.offer(next);  //큐에 넣음
                visit[next.x][next.y] += visit[cursor.x][cursor.y] + 1; //방문할때마다누적
            }
            //왼쪽
            if(cursor.y - 1 >= 0 && maze[cursor.x][cursor.y - 1] == 1 && visit[cursor.x][cursor.y - 1] ==0){
                Point next = new Point(cursor.x, cursor.y - 1);
                queue.offer(next);  //큐에 넣음
                visit[next.x][next.y] += visit[cursor.x][cursor.y] + 1;
            }
            //아래
            if(cursor.x + 1 < N && maze[cursor.x + 1][cursor.y] == 1 && visit[cursor.x + 1][cursor.y] ==0){
                Point next = new Point(cursor.x + 1, cursor.y);
                queue.offer(next);  //큐에 넣음
                visit[next.x][next.y] += visit[cursor.x][cursor.y] + 1;
            }
            //오른쪽
            if(cursor.y + 1 < M && maze[cursor.x][cursor.y + 1] == 1 && visit[cursor.x][cursor.y + 1] ==0){
                Point next = new Point(cursor.x, cursor.y + 1);
                queue.offer(next);  //큐에 넣음
                visit[next.x][next.y] += visit[cursor.x][cursor.y] + 1;
            }
            
        }//end while
        
        System.out.println(visit[N-1][M-1]);
 
    }
    
}