[백준] 1194번 : 달이 차오른다, 가자

1194번: 달이 차오른다, 가자.

 

---

[BFS + Bit Masking(비트마스킹)]

우선, 열쇠가 a, b, c, d, e, f 6개이므로 6자리 이진수의 최대값인 111111만큼의 visit 배열이 필요하다. 111111 = 63이다. 그러나 배열의 Index에 적용하기 위해선 +1을 해주어야 하므로 visit[64]개 만큼의 공간이 필요하다. 그럼 visit은 다음과 같이 정의될 수 있다.

 

boolean[][][] visit = new boolean[64][51][51];

 

열쇠가 하나도 없다면 000000 = 0

a열쇠가 있다면 000001 = 1

a, b열쇠가 있다면 000011 = 3

a, c, f열쇠가 있다면 100101 = 37

 

비트마스킹을 사용하면 위와 같이 0과 1만으로 어떤 열쇠를 습득했는지 알 수 있게 된다.

그럼 Queue에 넣어야할 원소는 4개가 된다.

1, 2) 다음 위치의 y, x좌표

3) 이동 횟수

4) 갖고있는 Key의 정보

 

그리고 BFS내부에서 가장 중요한 곳은 'a'~'f' 열쇠를 습득하는 곳과, 'A'~'F' 문을 방문할 때 이다.

만일 문을 방문했는데 적절한 열쇠가 없다면 더 이상 진행해서는 안되므로 열쇠를 갖고있는지 확인을 해야하고,

열쇠를 습득했다면 Key 정보에 해당 열쇠를 습득했다는 정보를 저장해야한다.

 

탈출구인 '1'을 방문했다면, 그 때의 이동 횟수를 비교하여 더 적은 쪽을 택하도록 한다.

 

//BFS의 일부 중 문을 방문할 때
                if(map[ny][nx] >= 'A' && map[ny][nx] <= 'F'){
                    if((nKey & (1 << map[ny][nx] - 'A')) != (1 << map[ny][nx] - 'A')) continue;
                    System.out.println(map[ny][nx] + "가 열렸습니다." + (cnt+1));
                }

//BFS일부 중 열쇠를 습득할 때
                else if(map[ny][nx] >= 'a' && map[ny][nx] <= 'f') {
                    //몇번째 비트를 set 시켜야하는지?
                    int whatKey = map[ny][nx] - 'a'; // map[ny][nx] - 97
                    nKey |= (1 << whatKey);
                }

//BFS일부 중 '1'을 방문할 때
                else if(map[ny][nx] == '1') {
                    min = Math.min(min, cnt + 1);
                }

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Point{
        int y, x, cnt, key;
        public Point(int yy, int xx, int c, int k){
            y=yy; x=xx; cnt=c; key = k;
        }
    }
    static int r, c, min = 1000000000;
    static boolean[][][] visit = new boolean[64][51][51];
    static char[][] map = new char[51][51];
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};

    static void BFS(Point start){

        Queue<Point> Q = new LinkedList<>();

        visit[0][start.y][start.x] = true;
        Q.add(new Point(start.y, start.x, 0, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();

            int cnt = p.cnt;

            for(int a=0; a<4; a++){
                int ny = p.y+Y[a];
                int nx = p.x+X[a];
                int nKey = p.key;

                if(ny < 1 || nx < 1 || ny > r || nx > c || visit[nKey][ny][nx] || map[ny][nx] == '#') continue;

                if(map[ny][nx] >= 'A' && map[ny][nx] <= 'F'){
                    if((nKey & (1 << map[ny][nx] - 'A')) != (1 << map[ny][nx] - 'A')) continue;
                }
                else if(map[ny][nx] >= 'a' && map[ny][nx] <= 'f') {
                    //몇번째 비트를 set 시켜야하는지?
                    int whatKey = map[ny][nx] - 'a'; // map[ny][nx] - 97
                    nKey |= (1 << whatKey);
                }
                else if(map[ny][nx] == '1') {
                    min = Math.min(min, cnt + 1);
                }

                visit[p.key][ny][nx] = true;
                visit[nKey][ny][nx] = true;
                Q.add(new Point(ny, nx, cnt + 1, nKey));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Point start = null;

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        for(int i=1; i<=r; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=c; j++){
                map[i][j] = str[j-1];

                if(map[i][j] == '0')
                    start = new Point(i, j, 0, 0);
            }
        }
        BFS(start);
        System.out.println(min != 1000000000? min:-1);
    }
}