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

BFS ...,,,,, 비트 마스크 .,,.,..

이거 어떻게 풀지 몰라서 다른 사람들 코드를 보고 이해한 후 풀었다.

비트마스크가 이렇게 쓰일 수 있다는 것이 너무 신기했다.

풀이

1.  BFS를 통해 탐색을 하면 된다.

2. 키의 개수가 a~f 까지, 6개이다. N과 M의 최대값은 50, 2^6은 64이므로 최대 50x50x64 이므로 배열을 만들어서 관리해도 크게 상관없다.

3. 해당위치에 어떤 키를 갖고 방문했는지 판단을 하여 재 방문 하지 않게 한다. 이때 비트마스크를 사용한다.

비트마스크를 이용한 키를 이용하는 방법은 2진수를 생각하면 된다.

키는 총 6개 비트는 6개를 사용한다. << , >> 이용한 shift 연산을 하면 해당 비트를 출력또는 변경 시킬 수 있다.

예를들어)

a키를 갖고 있을 경우는 100000 가 되고

a,b키를 갖고 있는 경우에는 110000

a,b,c키를 갖고 있는 경우 111000

모든 키를 갖고 있는경우는 111111이 된다.

이러한 비트마스크를 이용하여 문제를 풀어보자.

(1,1)에 a키를 갖고 방문했을 때는 Boolean check[1][1][0]에 접근하여 true로 값을 바꾼다.

이후 a키만 갖고 있을때는 Check[][][] 함수를 통해 (1,1)은 방문하지 않는다.

하지만 b키 또는 다른 키들을 획득한 후 (1,1)에 방문할 경우 Boolean check[1][1][1~64] 사이의 값을 접근하는 것이므로 (1,1)에 방문 할 수 있다.  

4. 위의 경우를 생각하여 문제를 풀면 된다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static int N;
    static int M;
    static char[][] arr;
    static boolean[][][] check;
 
    static int[] dx = { 1, -1, 0, 0 };
    static int[] dy = { 0, 0, 1, -1 };
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new
        // InputStreamReader(System.in));
 
        int Testcase = Integer.parseInt(br.readLine());
        for (int t = 1; t <= Testcase; t++) {
            String[] str = br.readLine().split(" ");
            N = Integer.parseInt(str[0]);
            M = Integer.parseInt(str[1]);
            Dot start = null;
            arr = new char[N][M];
            check = new boolean[N][M][1 << 6];
 
            for (int i = 0; i < N; i++) {
                str = br.readLine().split("");
                for (int j = 0; j < M; j++) {
                    arr[i][j] = str[j].charAt(0);
                    if (arr[i][j] == '0') {
                        start = new Dot(i, j, 0);
                    }
                }
            }
            System.out.print("#" + t + " ");
            System.out.println(BFS(start));
 
        }
    }
 
    public static int BFS(Dot start) {
        Queue<Dot> q = new LinkedList<Dot>();
        q.add(start);
        check[q.peek().x][q.peek().y][0] = true;
        int Hour = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int qsize = 0; qsize < size; qsize++) {
                Dot d = q.poll();
                int currentX = d.x;
                int currentY = d.y;
                int currentKey = d.key;
                System.out.println(currentX + " " + currentY);
                if (arr[currentX][currentY] == '1') {
                    return Hour;
                }
 
                for (int i = 0; i < 4; i++) {
                    int nextX = currentX + dx[i];
                    int nextY = currentY + dy[i];
                    int key = currentKey;
                    
                    //범위 밖이면 통과
                    if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M) {
                        continue;
                    }
                    // 벽을 만나면 통과
                    if (arr[nextX][nextY] == '#') {
                        continue;
                    }
                    //a 와 f 사이 키 일때 해당 위치의 값을 1로 만들어준다.
                    if ('a' <= arr[nextX][nextY] && arr[nextX][nextY] <= 'f') {
                        key |= (1 << arr[nextX][nextY] - 'a');
                    }
                    //A 와 F 사이 키를 갖고 있는지 확인한 후 없다면 패스한다.
                    if ('A' <= arr[nextX][nextY] && arr[nextX][nextY] <= 'F') {
                        if ((key & (1 << (arr[nextX][nextY] - 'A'))) == 0) {
                            continue;
                        }
                    }
                    //해당 위치에 똑같은 키들을 갖고 방문했다면 패스
                    if (check[nextX][nextY][key]) {
                        continue;
                    }
                    //해당 위치에 똑같은 키들을 갖고 방문한 적 없으면 방문 후, 재 방문 금지하기 위한 조건걸어둠.
                    check[nextX][nextY][key] = true;
                    q.add(new Dot(nextX, nextY, key));
                }
            }
            Hour++;
        }
        return -1;
    }
}
 
class Dot {
    int x;
    int y;
    int key;
 
    Dot(int x, int y, int key) {
        this.x = x;
        this.y = y;
        this.key = key;
    }
}