[BaekJoon] 1194 달이 차오른다, 가자 :: monton

문제

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

코드

가중치가 없고 최단 거리를 찾는 문제이므로 bfs를 사용

열쇠를 찾아서 출구로 나가야한다는 점이 특이한데 비트마스크를 이용하면 된다

큐를 쌓을때 4방향으로 뻗어가는 for 문에서 nkey을 변수로 안두고 했다가 고생했다 ㅠㅜ

열쇠를 찾아야 하므로 한번 지났던 곳을 다시 지날 수 있으므로 3차 배열로 visit을 두었다

풀이

#include <iostream>
#include <queue>
 
using namespace std;
 
int N, M,flag,ans;
char arr[51][51];
int bit[51][51][65];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
int main() {
    cin>> N >> M;
    
    queue <int> qx,qy,qk;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == '0') qx.push(i),qy.push(j),qk.push(0),bit[i][j][0]=1;
        }
    }
 
    while (!qx.empty()) {
 
        int cnt = qx.size();
        while (cnt--) {
            int x = qx.front();
            int y = qy.front();
            int key = qk.front();
            qx.pop(), qy.pop(), qk.pop();
            if (arr[x][y] == '1') {
                flag = 1;
                break;
            }
            //printf("x %d y %d\n", x, y);
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                int nkey = key;
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (arr[nx][ny]=='#') continue;
                if (arr[nx][ny] >= 'a'&&arr[nx][ny] <= 'f') {
                    nkey |= (1 << (arr[nx][ny] - 'a'));
                }
                if (arr[nx][ny] >= 'A'&&arr[nx][ny] <= 'F') {
                    if (!(nkey&(1 << (arr[nx][ny] - 'A')))) continue;
                }
                if (bit[nx][ny][nkey]) continue;
                qx.push(nx), qy.push(ny),qk.push(nkey);
                bit[nx][ny][nkey] = 1;
            }
        }
        if (flag) break;
        ans++;
    }
    if(flag) cout << ans;
    else cout << "-1";
}