(백준) 달이 차오른다, 가자 - 1194 [java]

https://www.acmicpc.net/problem/1194

 

🐢 설명

BFS + 비트마스킹 문제이다.

 

열쇠를 주운 경우의 수에 따라 탐색 시 방문처리를 다르게 해줘야 하므로 방문체크를 3차원배열로 해줘야한다. 이때 어떤 열쇠를 주웠는지 체크하는 용도로 비트마스킹을 사용하게 된다.

 

또한 열쇠를 줍고 자물쇠에 열쇠를 비교할 때 비트마스킹을 비교함으로써 자물쇠를 풀수있는지 확인할 수 있다.

 

참고로 방문 배열을 만들때는 (열쇠의 개수 + 1) 만큼 left shift를 해줘야 한다

• 만약 열쇠의 개수가 4개라면 최대 지닐 수 있는 열쇠는 1111이 될것이고 이때의 값은 15가 될것이다. 따라서 16크기의 배열이 필요하므로 (1 << 4 + 1) 을 해야 10000으로 16크기의 배열을 만들 수 있다.
• 즉 visited[y축][x축][1 << (자물쇠 개수 + 1)] 로 만들면 된다.

 

예를 들어보자

자물쇠 A, B, C, D를 비트로 표현하면 :  1 << ('자물쇠' - 'A')  이렇게 나타낼 수 있다.

A	B	C	D
1	10	100	1000

 

열쇠 a, b, c, d를 비트로 표현하면 위 방식과 동일하게 나타낼 수 있을 것이다 : 1 << ('열쇠' - 'a')

a	b	c	d
1	10	100	1000

 

그러면 내가 열쇠 b, d를 들고 있으면 어떻게 나타낼 수 있을까?

초기에는 열쇠를 하나도 들고 있지 않으므로 0일 것이고 b, d 열쇠를 만날 때마다 | (or) 연산을 통해서 해당 열쇠를 가졌다고 체크해 줄 수 있다. : 현재 키 보유 |= 1 << ('열쇠' - 'a')

열쇠 a, b를 가졌다면	열쇠 b, d를 가졌다면	열쇠 c, d를 가졌다면	열쇠 a, b, c, d를 가졌다면
11	1010	1100	1111

 

이렇게 열쇠를 가진 경우를 담아주고 자물쇠랑 비교해서 지나갈 수 있는지 없는지를 체크해자

열쇠로 자물쇠를 열수 있는지 비교하는 방법은 간단하다. &(AND) 연산을 통해서 해당 비트를 기존에도 가졌는지를 확인해주며 된다.
: { 현재 키 보유 & 1 << ('자물쇠' - 'A') } == 현재 키 보유

자물쇠 E	열쇠 보유 : a, c, e	자물쇠 & 열쇠보유 연산
10000	10101	10000 & 10101 == 10101

만약 자물쇠에 해당하는 열쇠를 보유하지 않았다면 &연산 시 값이 달라지게 될것이고 !=으로 확인해줄 수 있다.

 

🐢코드

public class 달이차오른다_가자_1194 {
    static char[][] board;
    static boolean[][][] visited;
    static int N, M;
    static int maxKey;
    static Dot start;
    private static class Dot {
        int y, x, d, k;

        public Dot(int y, int x, int d, int k) {
            this.y = y;
            this.x = x;
            this.d = d;
            this.k = k;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new char[N][M];
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                char c = s.charAt(j);
                if (c == '0') start = new Dot(i, j, 0, 0);
                if (c >= 'a' && c <= 'f') maxKey = Math.max(maxKey, c - 'a');
                board[i][j] = c;
            }
        }
        visited = new boolean[N][M][1 << (maxKey + 1)];
        int answer = go();
        System.out.println(answer);
    }

    private static int go() {
        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};
        PriorityQueue<Dot> pq = new PriorityQueue<>(Comparator.comparingInt(d -> d.d));
        start.k = 0;
        pq.add(start);
        visited[start.y][start.x][start.k] = true;

        while (!pq.isEmpty()) {
            Dot now = pq.poll();

            int cy = now.y;
            int cx = now.x;
            int ck = now.k;
            int cd = now.d;

            if (board[cy][cx] >= 'A' && board[cy][cx] <= 'F') {
                if ((ck | (1 << (board[cy][cx] - 'A'))) != ck) continue;
            }
            else if (board[cy][cx] >= 'a' && board[cy][cx] <= 'f') {
                ck |= 1 << board[cy][cx] - 'a';
            }
            else if (board[cy][cx] == '1') {
                return cd;
            }

            for (int d = 0; d < 4; d++) {
                int ny = cy + dy[d];
                int nx = cx + dx[d];

                if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
                if (board[ny][nx] == '#') continue;
                if (visited[ny][nx][ck]) continue;

                visited[ny][nx][ck] = true;
                pq.add(new Dot(ny, nx, cd + 1, ck));
            }
        }
        return -1;
    }
}

🐢 마무리

재밌는 비트마스킹을 활용한 문제였다.