2178 - 미로 탐색(bfs)

실버1 문제이다.

 

문제:

N, M 크기의 미로가 주어진다. 미로에서 1은 지나갈 수 있는 곳이고, 0은 막힌 곳이다.

(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하시오

 

 

풀이:

미로를 이동하는 방법은 무었일까? 당연하게도 지나갈 수 있는 길로 계속해서 이동하는 것이다.

그렇다면 최소 거리를 구하는 방법은 무엇일까? 다음 과정을 살펴보자.

 

1. 시작 위치는 (1,1)이다.

2. 시작위치에서 갈 수 있는 위치는 (2, 1) (1, 2)이다. 둘다 한칸만 이동하면 된다.

3. 이후 (1, 2)에서 이동 할 수 있는 위치는 (2, 2)이다.

4. (2, 1)에서 이동 가능한 위치는 (2, 2), (3,1) 이며, 이중 (2, 2)는 이동할 필요가 없다.
    이미 (1,1)에서 2번 이동해서 (2, 2)에 도착했기 때문이다.

5. (2, 2)에서 이동 가능한 위치는 (3, 2)이다.

6. (3, 1)에서 이동 할 수 있는 위치는 (3, 2)와 (4, 1)이며, 4번과 같은 이유로 (3, 2)에 갈 필요가 없다.

 

여기까지 왔다면, 이제 아래와 같은 규칙들을 발견 할 수 있을 것이다.

• 시작 위치부터 가까운 위치의 좌표부터 거리를 확인 할 것
• 한번 거리를 구한 좌표는 다시 거리를 구할 필요가 없다.

위 규칙들과 미로의 기본 규칙인 '0을 건너 뛸 순 없다', '미로 밖으로 이동 할 수 없다'를 합치면 문제를 풀 수 있을 것이다.

 

코드:

먼저 어떤 좌표까지 이동한 경우를 나타내는 클래스를 작성했다.

class Miro implements Comparable<Miro> {
    int y;
    int x;
    int sum;
    public Miro(int y, int x, int sum) {
        this.y = y;
        this.x = x;
        this.sum = sum;
    }
    @Override
    public int compareTo(Miro other) {
        return Integer.compare(this.sum, other.sum);
    }
}

y, x는 좌표를 나타내며, sum은 시작 좌표로부터 거리를 나타낸다.

Comparable 클래스를 상속받아, PriorityQueue와 함께 쓸 수 있도록 하자.

이렇게 사용하면 자신이 저장하길 원하는 정보들을, 편하게 정렬해서 볼 수 있다.

즉, 위 클래스는, sum을 기준으로 (y, x, sum) 이 세 정보를 정렬해준다.

 

미로 탈출 최소 거리를 구하는 메서드는 아래와 같다.

static int[] xMove = {1, -1, 0, 0};
static int[] yMove = {0, 0, 1, -1};
static PriorityQueue<Miro> routes;

static int bfs() {
    routes = new PriorityQueue<>();
    visited = new boolean[N][M];
    routes.add(new Miro(0,0,1));

    while (!routes.isEmpty()) {
        Miro miro = routes.poll();
        int y = miro.y;
        int x = miro.x;
        int sum = miro.sum;
        for (int i = 0; i < 4; i++) {
            int nextY = y+yMove[i];
            int nextX = x+xMove[i];
            if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
                if(!visited[nextY][nextX] && map[nextY][nextX] == 1) {
                    routes.add(new Miro(nextY, nextX, sum+1));
                    visited[nextY][nextX] = true;
                    if (y+yMove[i] == N-1 && x+xMove[i] == M-1) {
                        return sum+1;
                    }
                }
            }
        }
    }
    return 0;
}

xMove와 yMove의 사용에 대한 것은 다음 블로그에 정리해놓았다.

1303번 - 4방향 탐색(dfs) (tistory.com)

간단하게 말해 배열에 이동방향(동서남북)을 저장해놓고, 반복문으로 호출하는 방법이다.

 

1. 우선순위 큐에 시작 위치와 이동 횟수(1)을 저장한다. 이때, Miro 클래스를 이용하며, 들린 곳은 기록해놓는다(visited[][])

2. 다음 이동할 수 있는 좌표를 4방향 탐색을 사용해 선정한다.

3. 이동 할 수 있는 좌표를 유선순위 큐에 Miro 클래스를 이용해 저장한다. 이동 횟수 = 이전의 이동 횟수 + 1이다.

4. y좌표가 N-1, x좌표가 M-1에 도달할때 까지 2, 3번 과정이 반복되며,
   원하는 좌표에 도달하면, 그 좌표까지 가는데 필요한 이동 거리를 반환한다.

 

이렇게 반환은 한번만 이뤄지며, 그 반환 값이 최소 거리이다.

잘 보면 지금까지 이뤄진 과정이 bfs라는 것을 알 수 있을 것이다.

sum이 뜻하는 것은 노드의 깊이가 되는 것이며, 고로 원하는 목표값에 처음 도달하고 반환된 값이 최솟값이다.

정 이해가 가지 않으면 아래 그림을 한번 보면 이해 될 것이다.

bfs시, x 깊이에서 목표좌표를 찾았는데 굳이 최솟값보다 큰 x+1 깊이의 좌표를 탐색할 필요는 없다.

 

전체 코드는 아래와 같다.

import java.io.*;
import java.util.*;

class Miro implements Comparable<Miro> {
    int y;
    int x;
    int sum;
    public Miro(int y, int x, int sum) {
        this.y = y;
        this.x = x;
        this.sum = sum;
    }
    @Override
    public int compareTo(Miro other) {
        return Integer.compare(this.sum, other.sum);
    }
}

public class 미로탐색_2178번 {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int[] xMove = {1, -1, 0, 0};
    static int[] yMove = {0, 0, 1, -1};
    static PriorityQueue<Miro> routes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] dimensions = br.readLine().split(" ");
        N = Integer.parseInt(dimensions[0]);
        M = Integer.parseInt(dimensions[1]);

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        routes = new PriorityQueue<>();
        visited = new boolean[N][M];
        routes.add(new Miro(0,0,1));

        while (!routes.isEmpty()) {
            Miro miro = routes.poll();
            int y = miro.y;
            int x = miro.x;
            int sum = miro.sum;
            for (int i = 0; i < 4; i++) {
                int nextY = y+yMove[i];
                int nextX = x+xMove[i];
                if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
                    if(!visited[nextY][nextX] && map[nextY][nextX] == 1) {
                        routes.add(new Miro(nextY, nextX, sum+1));
                        visited[nextY][nextX] = true;
                        if (y+yMove[i] == N-1 && x+xMove[i] == M-1) {
                            return sum+1;
                        }
                    }
                }
            }
        }
        return 0;
    }
}