[백준 2178/JAVA] 미로 탐색

문제

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

2178번: 미로 탐색

최단거리는 BFS로 풀자

최단거리 찾기 문제는 BFS로 풀어야 한다.

 

BFS는 같은 거리에 있는 노드들을 다 처리한 뒤에 다음 거리의 노드를 탐색하러 가기 때문에, 각각의 노드가 시작 노드로부터 얼마나 떨어져있는지 하나 하나 기록해나가며 탐색하면 탐색이 모두 끝났을 때 바로 최단거리를 알 수 있다.

 

반면 DFS는 분기점이 생길 때마다 마지막 노드까지 갔다가 다시 분기점으로 돌아와서 마지막 노드까지 탐색하기를 반복하기 때문에, 자식 노드의 자식 노드를 탐색하며 마지막 노드까지 도달한 후 해당 경로의 거리 기록 -> 분기점으로 돌아와서 마지막 노드까지 도달한 후 해당 경로의 거리 기록 -> ... 이 작업을 반복해야 한다.  

 

DFS로 풀어도 최단거리를 구할 수야 있겠지만, 효율적이지 않은 방법이다. 코테에서 DFS로 최단거리 문제를 풀면 시간 초과가 뜰 위험이 있다.

 

풀이

앞서 말했듯이 이 문제는 BFS 탐색 원리를 적용해서 풀어야 한다.

 

먼저 arr[][]를 선언하고, 입력받은 값으로 초기화한다. 그러면 arr는 각각 0또는 1로 채워져있게 된다.
입력 예제 1의 경우, 아래 형태로 저장되어있을 것이다.
101111
101010
101011
111011

• 1은 이동 가능, 0은 이동 불가한 칸
• 인접한 칸으로만 이동 가능
• (1,1)에서부터 시작해서 (N,M)까지의 최단거리를 구해야 한다

arr의 (1,1)위치부터 BFS탐색을 시작한다.

BFS탐색이므로 현재 좌표와 거리가 같은 곳은 모두 방문해서 시작노드로부터 얼마 떨어져있는지 거리를 계산한 후 그 자리에 거리값을 저장한다. (나는 거리값을 저장할 배열을 따로 만들지 않고 그냥 arr에 값을 덮어씌웠다.)

 

먼저, 시작 좌표가 (1,1)이므로 큐에 (1,1)좌표를 넣은 후 방문 체크를 한다.

(나는 arr배열의 시작 좌표를 (0,0)로 대응시켜서 아래 구현코드에서는 bfs(0,0)으로 함수를 호출했다.)

큐를 사용한 이유는 아래에 설명해두었다.

 

그리고 큐가 빌 때까지 1~4번을 반복한다.

1. 큐에서 좌표 (x,y)를 하나 꺼냄 -> (x,y)와 인접한 좌표를 모두 구함. 즉, (x,y)의 상하좌우에 해당하는 좌표를 구함 (이하 (newX, newY))
2. (newX, newY)가 이동 가능한 곳이면 즉, 좌표가 NxM 크기를 벗어나지 않고, 값이 1이고, 아직 방문하지 않았다면
3. (newX, newY)방문 -> (newX, newY)을 큐에 넣음 -> 방문 체크
4. (newX, newY)가 (1,1)(=시작점)으로부터 떨어진 거리 계산하여 그 자리에 저장

• 인접한 좌표를 구해 어딘가에 적재한 후, 적재된 좌표를 다시 꺼내서 그곳을 기준으로 다시 인접 좌표를 탐색한다.
• 어딘가로 큐를 썼는데, 그 이유는 큐가 먼저 넣은 값부터 순서대로 꺼낼 수 있기 때문이다. 우리는 인접한 좌표를 모두 탐색한 후 다음 거리에 있는 좌표에 접근해야 한다. 큐를 쓰면 먼저 적재된 인접한 좌표들부터 순서대로 처리할 수 있다.
• 만약 임의의 좌표 (x,y)의 상하좌우에 이동 가능한 곳이 '2곳 이상'있다고 가정해보자. (입력 예제 1의 (1,5)위치에 해당하는 경우이다. 이 좌표는 오른쪽과 아래쪽 두 곳을 방문할 수 있다.) 이때는 가장 먼저 들어온 값부터 꺼내지 않으면 너비우선탐색을 할 수 없다. 
• 큐에 좌표를 저장하기 위해 변수로 x, y를 가지는 Coordinate라는 클래스를 만들었다. 이 클래스의 객체를 생성해서 큐에 저장한다.
• bfs를 수행하는 코드는 따로 빼서 bfs 함수로 선언했다.

 

코드

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

public class Main {
    static int N, M;
    static int[][] arr;
    static boolean[][] check;
    static Queue<Coordinate> q = new LinkedList<>();


    public static void main(String[] agrs) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //N, M
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];
        check = new boolean[N][M];

        //행렬 초기화
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++){
                arr[i][j] = str.charAt(j)-48;
            }
        }

        bfs(0,0);
        bw.write(arr[N-1][M-1] + " ");//마지막 지점의 값을 출력하면 됨
        bw.close();
    }

    static void bfs(int x, int y) {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        //좌표를 받아서 객체 생성, 큐에 삽입
        q.offer(new Coordinate(x,y));
        check[x][y] = true;

        while(!q.isEmpty()) {            
            Coordinate c = q.poll(); //큐에서 객체 하나 꺼내기

            for(int i=0; i<4; i++) { //꺼낸 객체 좌표의 상하좌우 확인
                int newX = c.x + dx[i];
                int newY = c.y + dy[i];

                if(newX<0 || newX>=N || newY<0 || newY>=M) //새로운 좌표가 N*M 범위를 넘는 노드 제외
                    continue;

                if(arr[newX][newY]==0 || check[newX][newY]) //값이 0이고, 이미 방문한 노드 제외
                    continue;

                arr[newX][newY] = arr[c.x][c.y] + 1; //새로운 좌표에 지나온 노드 수 저장
                q.offer(new Coordinate(newX,newY)); //새로운 좌표의 객체 생성, 큐에 삽입
                check[newX][newY] = true;
            }

        }
    }
}

class Coordinate{
    int x;
    int y;

    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}