[백준/1194번/Java] 달이 차오른다, 가자.

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

 

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

 

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막 기회다. 이걸 놓치면 영영 못 간다.

 

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

 

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

 

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

 

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

입출력 예

input	output
1 7 f0.F..1	7
5 5 ....1 #1### .1.#0 ....A .1.#.	-1
7 8 a#c#eF.1 .#.#.#.. .#B#D### 0....F.1 C#E#A### .#.#.#.. d#f#bF.1	55

---

풀이에 사용할 알고리즘 구상

32개 미만의 열쇠와 문이 있다는 것을 보고 비트마스킹을 사용했다! (문제에선 6개다.)

근데 정작 중요한 것은, 열쇠를 주운 경우 왔던 길을 다시 돌아가야 하는 경우가 있다.

그렇다면, 열쇠를 먹은 시점에서 visited 배열을 초기화해야 하나? 하는 의문점이 들었다.

지나온 길은 visited 배열에서 true이기 때문에 열쇠를 먹은 순간 왔던 길로 되돌아갈 수 없기 때문이다.

 

그래서 막무가내로, 열쇠를 먹으면 visited 배열을 초기화하고 열쇠가 있던 자리만 visited 배열의 값을 true로 바꾸는 방법을 사용했다.

하지만 결과는 당연하게도 실패였다. 이유는 다음과 같다.

 

1. BFS를 Queue를 사용해서 구현했는데, 다른 열쇠를 먹으러 가는 길인 경우가 Queue의 앞에 위치해서 내가 돌아가야 할 길의 visited 값을 true로 만들어버리는 경우가 있다.
2. 열쇠가 2개 이상일 경우 서로 다른 열쇠를 먹을 때마다 visited 배열이 초기화되어 정상적인 너비 우선 탐색이 불가능해진다.
   위에서 언급한 문제 말고도 여러 문제가 발생했기 때문에 이 아이디어는 폐기되었다.

해결 방안을 찾지 못하여 구글링을 살짝 해봤다. 그리고 엄청나게 획기적인 아이디어를 알게 되었다.

 

각 비트마스킹 경우마다 visited 배열을 따로 두면 된다.

 

이렇게 할 경우 열쇠를 먹을 때마다 visited 배열을 초기화하면서도, 각 비트마스킹 경우마다 서로 다른 visited 배열을 가지게 되므로 위에서 언급한 문제가 전부 해결된다.

다만 정말 64개(2⁶. 문제에서 가능한 모든 비트마스킹 경우의 수)의 N * M 크기의 visited 배열을 만들 필요는 없고, visited 배열을 3차원 배열로 만들어서 마지막 index는 각 비트마스킹의 경우로 사용하면 된다.

 

이런 기법은 다음에도 유용하게 사용할 수 있을 것 같다고 생각했다.

 

결론

이 문제의 핵심을 두 줄로 요약하면 다음과 같다!

1. 비트마스킹을 사용한다.
2. visited 배열을 3차원 배열로 사용한다.

 

제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Info {
    int x;
    int y;
    int bitmask;
    int moveCount;

    public Info(int x, int y, int bitmask, int moveCount) {
        this.x = x;
        this.y = y;
        this.bitmask = bitmask;
        this.moveCount = moveCount;
    }
}

public class Main {
    static int N, M;
    static char[][] maze;
    static boolean[][][] visited;
    static int[][] direction = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};

    static int bfs(Info info) {
        visited[info.x][info.y][0] = true;
        Queue<Info> queue = new LinkedList<>();
        queue.add(info);
        while (!queue.isEmpty()) {
            Info top = queue.poll();
            visited[top.x][top.y][top.bitmask] = true;
            for (int i = 0; i < 4; i++) {
                int newX = top.x + direction[i][0];
                int newY = top.y + direction[i][1];
                if (newX >= 0 && newY >= 0 && newX < N && newY < M) {
                    if (!visited[newX][newY][top.bitmask]) {
                        switch(maze[newX][newY]) {
                        case '1':
                            return top.moveCount + 1;
                        case '0':
                        case '.':
                            visited[newX][newY][top.bitmask] = true;
                            queue.add(new Info(newX, newY, top.bitmask, top.moveCount + 1)); // break 안해도 아래서 걸림
                        case '#':
                            break;
                        case 'a':
                        case 'b':
                        case 'c':
                        case 'd':
                        case 'e':
                        case 'f':
                            visited[newX][newY][top.bitmask] = true;
                            queue.add(new Info(newX, newY, top.bitmask | 1 << 'f' - maze[newX][newY], top.moveCount + 1));
                            break;
                        case 'A':
                        case 'B':
                        case 'C':
                        case 'D':
                        case 'E':
                        case 'F':
                            visited[newX][newY][top.bitmask] = true;
                            // 맞는 열쇠가 없다ㅠㅠ
                            if (((top.bitmask) & (1 << 'F' - maze[newX][newY])) == 0) break;
                            // 맞는 열쇠가 있다ㅎㅎ
                            else queue.add(new Info(newX, newY, top.bitmask, top.moveCount + 1));
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        maze = new char[N][M];
        visited = new boolean[N][M][64];
        for (int i = 0; i < N; i++) maze[i] = br.readLine().toCharArray();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (maze[i][j] == '0') System.out.println(bfs(new Info(i, j, 0, 0)));
            }
        }
    }
}
}