문제해결

벽 부수고 이동하기, 말이 되고픈 원숭이
같은 유형의 더 난이도가 낮은 문제들 입니다.

미로에서 최단경로를 찾는 문제이지만 열쇠와 문을 사용해 조건을 까다롭게 만들어놓은 문제이다. 6개의 열쇠 a, b, c, d, e, f와 6개의 문 A, B, C, D, E, F는 각 문에 해당하는 열쇠가 있어야 문을 통과할 수 있다. 따라서 가지고 있는 열쇠 조합에 따라 맵에서 갈 수 있는 경로가 달라지기 때문에 열쇠를 가지고 있을 수 있는 모든 경우에 대해 각각 다르게 방문 배열을 체크해줘야 한다. (a만 가지고 있는경우 b만 가지고 있는경우 a, b만 가지고 있는경우 등등 각각의 경우에 따라 갈 수 있는 맵의 위치가 달라지기 때문)
열쇠는 총 6개 이므로 열쇠가 아무것도 없는 경우부터 6개의 열쇠가 전부다 있는 경우까지 부분집합의 개수와 같으므로 총 2ⁿ(n = 6) -> 64개의 경우의 수가 있다.
따라서 맵의 크기가 N * M 일때 방문처리 배열의 크기는 visit[N][M][64]가 된다.
여기서 0 ~ 63의 인덱스가 각각 어떤 열쇠를 가지고 있는 경우인지 체크를 해줘야 하는데 이는 비트마스킹으로 쉽게 해결할 수 있다.

BFS, 비트마스킹

컴퓨터는 데이터를 저장할때 항상 이진수로 저장을 한다. 프로그래밍 할때 선언되는 10 진수의 정수형 변수도 역시 마찬가지로 이진수로 저장이 되는데 이진수의 0과 1의 조합으로 구성되어지는 특성을 활용하면 부분집합을 마킹하는것처럼 사용할 수 있다.
예를 들어 f, e, d, c, b, a 순서로 열쇠가 있을때 1, 없을때 0으로 표시를 하고 c, a 열쇠만 가지고 있다고 해보자. 이것을 이진수로 표현하면 000101 이고 이것을 10진수로 표현하면 5가 된다. 따라서 visit[N][M][5]에는 c, a 열쇠를 가지고 있는 경우의 방문처리 배열이라고 볼 수 있다.
이 방법을 사용하려면 5라는 값은 c, a 열쇠를 가지고 있는 경우라는것을 알아야하고, 추가로 열쇠를 찾는 경우 값이 어떻게 바뀌는지를 알아야 한다. 이것은 비트연산을 통해 가능하다. 비트연산자는 총 6개가 있으며 그 의미는 다음과 같다.

만약 열쇠를 가지고 있는 값이 5(000101) 라면 c, a 열쇠를 가지고 있는것이고 각 문을 지날때 & 연산을 사용해 키를 가지고 있는지 확인할 수 있고, 열쇠를 지날때 | 연산을 사용해 key 값을 바꿀 수 있다.
예를 들어 A나 E 문을 지날때는 000101과 000001, 010000 을 & 연산을 통해 열쇠 a는 가지고 있지만 열쇠 e는 없다는 것을 알 수 있고, a 나 e 열쇠를 지날때는 000101과 000001, 010000 을
| 연산을 통해 열쇠를 추가해주면 된다.

000101 & 000001 = 000001 -> 열쇠 a를 가지고 있음
000101 & 010000 = 000000 -> 열쇠 e를 가지고 있지 않음
000101 | 000001 = 000101 -> 열쇠 a를 획득 (a, c 보유)
000101 | 010000 = 010101 -> 열쇠 e를 획득 (a, c, e 보유)

시간복잡도

최대 크기가 N * M인 맵을 최대 64번 탐색해야 하므로 최대 64 * N * M 번의 연산이 필요하다. 따라서 시간복잡도는 64(N * M) 이다 (N, M <= 50)

소스코드

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

public class Main {
    static int N, M, d_row[] = {0, 0, 1, -1}, d_col[] = {1, -1, 0, 0}, min = -1;
    static char map[][];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new char[N][M];

        int row = 0, col = 0;
        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = temp.charAt(j);
                if (map[i][j] == '0') {
                    row = i;
                    col = j;
                }
            }
        }
        bfs(row, col);
        bw.write(String.valueOf(min));
        bw.flush();
        bw.close();
    }

    static void bfs(int row, int col) {
        Queue<node_1194> queue = new LinkedList<>();
        boolean visit[][][] = new boolean[N][M][64];
        queue.offer(new node_1194(row, col, 0, 0));
        visit[row][col][0] = true;

        while (!queue.isEmpty()) {
            node_1194 n = queue.poll();

            for (int i = 0; i < 4; i++) {
                int r = n.row + d_row[i], c = n.col + d_col[i], d = n.distance + 1, k = n.key;
                if (r < 0 || c < 0 || N <= r || M <= c || map[r][c] == '#') continue;
                char load = map[r][c];
                if (load == '1') {
                    min = d;
                    return;
                }
                if ('A' <= load && load <= 'F' && (1 << (load - 'A') & k) != 1 << (load - 'A')) continue;
                if ('a' <= load && load <= 'f') k = k | 1 << (load - 'a');
                if (visit[r][c][k]) continue;
                queue.offer(new node_1194(r, c, d, k));
                visit[r][c][k] = true;
            }
        }
    }
}

class node_1194 {
    int row, col, distance, key;
    node_1194(int row, int col, int distance, int key) {
        this.row = row;
        this.col = col;
        this.distance = distance;
        this.key = key;
    }
}