[boj] 백준 1194 달이 차오른다, 가자 (c++) - 비트마스킹, BFS

[문제]

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

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

 

[풀이]

보통의 BFS, DFS 문제에서 추가로 고려해줘야 할 부분은 크게 다음 2가지이다.

 

1) 똑같은 위치라도 key가 없는 상태에서 방문한 것과 key가 있는 상태에서 방문했을 때가 다르다. 이를 구분해주기 위해 visited[][][key]와 같이 3차원으로 선언하여 현재 소지한 키의 상태를 저장할 수 있도록 한다.

 

2. 6개의 열쇠 소지 여부에 대한 관리가 필요하다. 이를 위해 비트마스킹을 이용한다. 비트마스킹이 이용되는 부분을 좀 더 자세히 살펴보자! (참고로, 비트마스킹 기법은 우리가 관리하고자 하는 값을 2진수 비트로 나타내는 것이지만 실제 저장되는 값은 int로 저장하고 있다.) 

먼저 이 문제에서는 a~f 의 열쇠를 가지고 있다면, 열쇠와 일치하는 알파벳인 A~F 문에 도달했을 때 문을 열고 이동이 가능하다.

1) 따라서 a~f 의 열쇠가 있는 위치에 도달했을 때 해당 열쇠를 얻었음을 저장해줘야 한다. 해당 열쇠를 추가적으로 얻는 것이므로 현재의 열쇠 소지 상태와 OR 연산(&)을 해주면 된다. 

예를 들어, 현재 a 열쇠를 가지고 있다면 열쇠 소지 상태는 000001 이다. 이 상태에서 f 열쇠를 획득했다면 현재 상태인 000001과 100000을 OR 연산(|)하면 된다. 그렇다면 어떻게 f 열쇠를 얻었음을 100000과 같이 나타낼 수 있을까? 바로 알파벳의 인덱스만큼 1을 shift 연산(<<) 해주면 된다. 즉 'f' - 'a' (아스키 코드) = 5 이고, 5만큼 1을 shift 해주면 100000 이 된다.

2) A~F 문의 위치에 도달했다면 일치하는 열쇠를 가지고 있는지를 보고 이동할 수 있는지 판단해야 한다.  문에 해당하는 알파벳과 일치하는 열쇠를 가지고 있는지를 판단해야 하므로 AND 연산(&)을 해줘야 한다.

예를 들어, B 문이라면 000010 과 같이 나타낼 수 있다. 이때 B 열쇠를 가지고 있다면 000010과 000010을 AND 연산해 1이 나오므로 참으로 볼 수 있다. 그러나 만약 A열쇠와 F 열쇠만 가지고 있다면 000010과 100001의 AND 연산이므로 0이 되어 이동할 수 없다.

 

[코드]

 

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace::std;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};

struct node{
    int x, y;
    int count;
    int key;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m;
    char maze[50][50];
    bool visited[50][50][64] = {false, }; //2^6, 6개의 열쇠 유뮤 표시
    queue<node> q;

    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> maze[i][j];
            if(maze[i][j]=='0'){
                node start;
                start.x = i;
                start.y = j;
                start.count = 0;
                start.key = 0;
                q.push(start);
            }
        }
    }

    while(!q.empty()){
        node v = q.front();
        q.pop();
        int x = v.x;
        int y = v.y;
        int key = v.key;
        int count = v.count;

        if(maze[x][y]=='1'){
            cout << count;
            return 0;
        }

        for(int i=0; i<4; i++){
            int newx = x + dx[i];
            int newy = y + dy[i];

            if (newx < 0 || newx >= n || newy < 0 || newy >= m) continue;
            if(maze[newx][newy]=='#') continue; //#: 벽

            //a~f 열쇠일 때 - 열쇠가 있는 상태에서 방문한 게 아닌 경우 상태 업데이트 후 저장
            if('a' <= maze[newx][newy] && maze[newx][newy] <= 'f'){
                int newkey = key | (1 << (maze[newx][newy]-'a'));

                if(visited[newx][newy][newkey]) continue; //열쇠를 가지고 이미 방문한 경우

                node next;
                next.x = newx;
                next.y = newy;
                next.key = newkey;
                next.count = count + 1;
                q.push(next);

                visited[newx][newy][newkey] = true;
            }
            //A~F 문일 때 - 가지고 있는 열쇠가 비교해서 문을 열 수 있는지 확인
            else if('A' <= maze[newx][newy] && maze[newx][newy] <= 'F'){
                int open = key & (1 << (maze[newx][newy]-'A'));

                if(!open || visited[newx][newy][key]) continue;

                node next;
                next.x = newx;
                next.y = newy;
                next.key = key;
                next.count = count + 1;
                q.push(next);

                visited[newx][newy][key] = true;
            }
            //.인 경우 - 방문하지 않았다면
            else if(!visited[newx][newy][key]){
                node next;
                next.x = newx;
                next.y = newy;
                next.key = key;
                next.count = count + 1;
                q.push(next);

                visited[newx][newy][key] = true;
            }
        }
    }
    cout << "-1"; //미로를 탈출할 수 없는 경우
}