백준 - 1194번(달이 차오른다, 가자.)

문제 출처: https://www.acmicpc.net/problem/1194

문제

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

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

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

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

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

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

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static class Node {

        int row;
        int col;
        int cnt;
        int keyStatus;

        public Node(int row, int col, int cnt, int keyStatus) {
            this.row = row;
            this.col = col;
            this.cnt = cnt;
            this.keyStatus = keyStatus;
        }

    }

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

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int[][] directions = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

        int N = Integer.parseInt(tokenizer.nextToken()); // 세로(행)
        int M = Integer.parseInt(tokenizer.nextToken()); // 가로(열)

        int startR = 0, startC = 0;
        boolean flag = false;

        char[][] matrix = new char[N][M];
        for (int i = 0; i < N; i++) {
            matrix[i] = reader.readLine().toCharArray();
            if (!flag) {
                for (int j = 0; j < M; j++) {
                    if (matrix[i][j] == '0') {
                        startR = i;
                        startC = j;
                        flag = true;
                        break;
                    }
                }
            }
        }

        boolean[][][] visited = new boolean[N][M][64];

        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(startR, startC, 0, 0));

        while (!queue.isEmpty()) {
            Node node = queue.poll();

            if (visited[node.row][node.col][node.keyStatus]) continue;
            if (matrix[node.row][node.col] == '1') {
                System.out.println(node.cnt);
                return;
            }

            visited[node.row][node.col][node.keyStatus] = true;

            for (int i = 0; i < 4; i++) {
                int dy = node.row + directions[i][0];
                int dx = node.col + directions[i][1];

                if (dy >= 0 && dy < N && dx >= 0 && dx < M) {
                    if (visited[dy][dx][node.keyStatus]) continue;
                    if (matrix[dy][dx] == '.' || matrix[dy][dx] == '0' || matrix[dy][dx] == '1') queue.offer(new Node(dy, dx, node.cnt + 1, node.keyStatus));
                    else if (matrix[dy][dx] >= 'a' && matrix[dy][dx] <= 'f') queue.offer(new Node(dy, dx, node.cnt + 1, node.keyStatus | 1 << matrix[dy][dx] - 'a'));
                    else if (matrix[dy][dx] >= 'A' && matrix[dy][dx] <= 'F') {
                        if ((node.keyStatus & 1 << matrix[dy][dx] - 'A') != 0) {
                            queue.offer(new Node(dy, dx, node.cnt + 1, node.keyStatus));
                        }
                    }
                }
            }
        }

        System.out.println(-1);
    }

}

• 비트 마스킹을 사용하는 다소 까다로운 문제였다.
• 현재의 위치에서 4방 탐색을 통해 갈 방향을 찾는데, 이때 열쇠를 가진 상태에 따라 경우가 나뉘게 된다. 다시 말해, 열쇠를 가진 상태가 다르면 다른 상황으로 보아 이 상황에 따라 방문 처리를 해줘야한다.
• 열쇠는 6가지이므로 6가지의 상황을 기록하기 위해 2의 6승인 64 크기로 3차원 배열 마지막 크기 값으로 설정하였다.
• 미로를 탐색하다가 길이 막히면 더 이상 진행하지 않고, 만약 열쇠를 먹은 경우에는 다시 돌아올 수 있다.