[c++][백준 1194] 달이 차오른다, 가자.

백준 1194번: 달이 차오른다, 가자. [Gold1]
https://www.acmicpc.net/problem/1194

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

문제 풀이

• 이 문제는 BFS + 비트마스킹으로 구현했습니다. 
• key를 비트마스킹으로 관리했는데, 아래와 같이 두 가지 경우가 있습니다.
  • 'a' ~ 'f'를 만날 경우 key |= 1 << (maze[y][x] - 'a') -> 열쇠를 집음
  • 'A' ~ 'F'를 만날 경우 key & 1 << (maze[y][x] - 'A') -> 열쇠가 있을 경우를 확인
• visited는 key의 상태에 따라 관리 -> visited[50][50][1<<6]

코드

#include <cstdio>
#include <cctype>
#include <queue>
#include <tuple>

using namespace std;

char maze[50][50];
int visited[50][50][1<<6];
int N, M;

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

bool safe(int y, int x) {
    return y>=0 && x>=0 && y<N && x<M;
}

int main() {
    scanf("%d %d", &N, &M);
    int sy, sx;
    for(int i=0; i<N; ++i) {
        getchar();
        for(int j=0; j<M; ++j) {
            maze[i][j] = getchar();
            if(maze[i][j] == '0') {
                sy = i;
                sx = j;
            }
        }
    }

    // count, y, x, key
    priority_queue<tuple<int,int,int,int>> pq;
    pq.push({0, sy, sx, 0});
    int answer = 1e9;

    while(!pq.empty()) {
        auto [cnt, y, x, k] = pq.top(); pq.pop();
        cnt = -cnt;
        
        if(maze[y][x] == '1') {
            answer = cnt;
            break;
        }

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

            if(!safe(ny, nx) || maze[ny][nx] == '#') continue;
            
            // 문을 만났는데 키가 없을 경우 continue
            if(isupper(maze[ny][nx]) && !(k & (1 << (maze[ny][nx] - 'A')))) continue;

            int key = k;
            
            // 열쇠 만나면 집음
            if(islower(maze[ny][nx])) {
                key |= 1 << (maze[ny][nx] - 'a');
            }

            if(!visited[ny][nx][key]) {
                visited[ny][nx][key] = 1;
                pq.push({-(cnt+1), ny, nx, key});
            }
        }
    }

    if(answer == 1e9) printf("-1");
    else printf("%d", answer);

    return 0;
}

실행 결과