[이코테 with Java] 미로 탈출(BFS)

문제

동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 

동빈이의 위치는 (1, 1) 이고, 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 

이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다.

이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 

입력 조건

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력 조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
1 0 1 0 1 0
1 1 1 1 1 1
0 0 0 0 0 1
1 1 1 1 1 1
1 1 1 1 1 1

 

출력 예시

10

 

1인 곳에서만 이동할 수 있는데, 최소 칸을 구해야 하므로, 

(1,1) -> (2, 1) ~ (2, 6) -> (3, 6) -> (4, 6) -> (5, 6) 순으로 이동하면 된다. 

---

코드

import java.util.*;

class Node {
    private int x;
    private int y;

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

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }
}

public class Main {
    public static int n, m;
    public static int[][] graph = new int[201][201];

    // 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};



    public static int bfs(int x, int y) {
        // 큐(Queue) 구현을 위해 queue 라이브러리 사용
        Queue<Node> q = new LinkdedList<>();
        q.offer(new Node(x, y));
        // 큐가 빌 때까지 반복하기
        while(!q.isEmpty()) {
            Node node = q.poll();
            x = node.getX();
            y = node.getY();
            // 현재 위치에서 4가지 방향으로의 위치 확인
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 미로 찾기 공간을 벗어난 경우 무시
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                // 벽인 경우 무시
                if(graph[nx][ny] == 0) continue;
                // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                if(graph[nx][ny] == 1) {
                    graph[nx][ny] = graph[x][y] + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }
        // 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[n - 1][m - 1];
    }

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

        // N, M을 공백을 기준으로 구분하여 입력 받기
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기

        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i< n; i++){
            String str = sc.nextLine();
            for(int j =0; j < m; j++){
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        // BFS를 수행한 결과 출력
        System.out.println(bfs(0,0));
    }

 

1. 미로의 한 지점(노드)를 나타낼 개념을 캡슐화한다.

class Node {
    private int x;
    private int y;

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

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }
}

 

2. n행과 m열, 전체 미로의 크기인 graph 배열, 이동할 네 가지 방향인 dx와 dy를 선언해준다. 

    public static int n, m;
    public static int[][] graph = new int[201][201];

    // 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};

 

3. 큐(Queue)에 첫 번째 노드를 넣어주고, 큐가 빌 때가지 노드의 x좌표와 y좌표를 출력하고, 

네 가지 방향(상하좌우)로 미로 찾기의 공간을 벗어나거나 벽이 아닌 경우 해당 노드를 +1로 처리해준다. 

그리고 해당 노드를 큐에 추가해준다.

마지막으로 가장 오른쪽 아래까지의 최단 거리를 반환해주는데, -1을 해주는 이유는 크기보다 인덱스가 1씩 작기 때문이다.

public static int bfs(int x, int y) {
        // 큐(Queue) 구현을 위해 queue 라이브러리 사용
        Queue<Node> q = new LinkdedList<>();
        q.offer(new Node(x, y));
        // 큐가 빌 때까지 반복하기
        while(!q.isEmpty()) {
            Node node = q.poll();
            x = node.getX();
            y = node.getY();
            // 현재 위치에서 4가지 방향으로의 위치 확인
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 미로 찾기 공간을 벗어난 경우 무시
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                // 벽인 경우 무시
                if(graph[nx][ny] == 0) continue;
                // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
                if(graph[nx][ny] == 1) {
                    graph[nx][ny] = graph[x][y] + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }
        // 가장 오른쪽 아래까지의 최단 거리 반환
        return graph[n - 1][m - 1];
    }

 

5. 전체 n행과 m열을 입력받고, 리스틩 맵 정보를 입력받는다.

(0,0)부터 bfs를 수행한 결과를 출력한다.

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

        // N, M을 공백을 기준으로 구분하여 입력 받기
        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine(); // 버퍼 지우기

        // 2차원 리스트의 맵 정보 입력 받기
        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = str.charAt(j) - '0';
            }
        }

        // BFS를 수행한 결과 출력
        System.out.println(bfs(0, 0));
    }

 

그렇다면 왜 DFS가 아닌 BFS를 사용해야 할까?

왜냐하면 가장 가까운 노드가 나오면 바로 변경해야 하기 때문이다.

 

DFS를 사용한다고 생각해보자.

최단 거리가 아닌 한 경로를 끝까지 탐색한 결과를 얻게 될 것이다.

따라서 한 경로를 끝까지 탐색하기 대문에 최단 경로를 보장하지 않는다.

 

BFS를 사용하면 가장 가까운 노드가 나오면 바로 경로를 변경해준다.

따라서 한 경로만 파는 것이 아니라, 가까운 다른 노드가 나오면 경로를 변경하기 때문에 

최단 거리를 구할 때 유리하다.