[Algorithm/C++17] 백준 1194 달이 차오른다, 가자

문제

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

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

풀이 방법

2206번 벽 부수고 이동하기와 비슷한 문제이다. 이 문제에서는 벽을 부수는 것이 아니라 열쇠로 이동하면 열쇠를 획득하여 해당하는 문을 열 수 있는 것이 특징이다. 따라서 큐에 좌표와 갖고 있는 키 상태를 넣어줘야 하며, 방문도 마찬가지로 키를 갖고있는 상태에서 방문한 좌표를 체크해줘야한다. (3차원 공간)

키를 갖고 있는 것을 어떻게 표현해야할지가 문제인데, 총 개수가 6이므로 비트마스킹을 사용하여 표현한다. 낮은 비트부터 시작하여 a~f의 키를 갖고 있으면 1, 갖고 있지 않으면 0으로 나타낸다.

예를 들면, 100 000이면 f키만을 갖고 있는 것이고, 011 011이면 a, b, d, e 키를 갖고 있는 것이다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};
int main()
{
    int N, M;
    char c;
    scanf("%d %d", &N, &M);
    vector<vector<char>> v(N, vector<char>(M, '.'));
    bool visited[64][51][51] = {false,};
    queue<tuple<int,int,int,int>> q;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            scanf(" %1c", &c);
            v[i][j] = c;
            if(c=='0')
            {
                q.push({i,j,0,0});
                v[i][j] = '.';
            }
        }
    }
    
    bool success = false;
    int answer = -1;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        int y = get<0>(t);
        int x = get<1>(t);
        int keys = get<2>(t);
        int count = get<3>(t);
        if(v[y][x] == '1')
        {
        	success = true;
        	answer = count;
        	break;
        }
        for(int i=0; i<4; i++)
        {
            if(success) break;
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(0<=ny && ny<N && 0<=nx && nx<M)
            {
                if(visited[keys][ny][nx]) continue;
                if(v[ny][nx] == '.' || v[ny][nx] == '1')
                {
                    visited[keys][ny][nx] = true;
                    q.push({ny,nx,keys,count+1});
                }
                else if('a'<= v[ny][nx] && v[ny][nx] <='f')
                {
                    int k = v[ny][nx]-'a';
                    int new_keys = keys | (1<<k);
                    visited[new_keys][ny][nx] = true;
                    q.push({ny,nx,new_keys,count+1});
                }
                else if('A'<= v[ny][nx] && v[ny][nx] <='F')
                {
                    int k = v[ny][nx]-'A';
                    int hasKey = keys & (1<<k);
                    if(hasKey) 
                    {
                    	visited[keys][ny][nx] = true;
                        q.push({ny,nx,keys,count+1});
                    }
                }
            }
        }
    }
    
    printf("%d", answer);
    return 0;
}

고찰

비트마스킹 개념이 어렵진 않지만 연산자로 표현할 때 은근히 헷갈리기 때문에 주의해야 한다.

int status = 0b01100110; // 예시

// 1. k번 비트가 1인지 0인지 확인
int result = status & (1<<k);
// k번 비트가 1이었다면 1<<k
// k번 비트가 0이었다면 0이 저장된다.

// 2. k번 비트를 1로 만들기
status = status | (1<<k)

// 3. k번 비트를 0으로 만들기
status = status & ~(1<<k)