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

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

문제 링크

#include "header.h"
using namespace std;
int N, M;
char board[51][51];
int visit[51][51][1 << 7];
pair <int, int> minsik;
typedef struct node
{
    int x;
    int y;
    int dis;
    int key;
}node;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void input(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> board[i][j];
            if(board[i][j] == '0'){
                minsik = {i, j};
                board[i][j] = '.';
            }
        }
    }
}

void solve(){

    queue <node> q;

    q.push({minsik.first, minsik.second,0,0});
    visit[minsik.first][minsik.second][0] = 1;

    while (!q.empty()){
        int top_x = q.front().x;
        int top_y = q.front().y;
        int dis = q.front().dis;
        int key = q.front().key;
        q.pop();

        if(board[top_x][top_y] == '1'){
            cout << dis << endl;
            return;
        }

        for(int i=0; i<4; i++){
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];
            if(visit[nx][ny][key] || board[nx][ny] == '#' || nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

            if(isupper(board[nx][ny])){
                if (key & 1 << (board[nx][ny] - 'A')){
                    visit[nx][ny][key] = 1;
                    q.push({nx, ny, dis+1, key});
                    continue;
                }
            }else if(islower(board[nx][ny])){
                int check_key = key | (1 << (board[nx][ny] - 'a'));
                if(!visit[nx][ny][check_key]){
                    visit[nx][ny][check_key] = 1;
                    visit[nx][ny][key] = 1;
                    q.push({nx, ny, dis+1, check_key});
                    continue;
                }
            }else{
                q.push({nx, ny, dis+1, key});
                visit[nx][ny][key] = 1;

            }
        }
    }

    cout << -1 << endl;
    
}
int main() {
    input();
    solve();
    
    return 0;
}

• bfs + 비트마스킹 문제
• 원래는 key랑 door를 map으로 둬서, 비트마스킹 대신 사용해 보려고 했는데, 상태 보존이 힘들어서 비트마스킹을 참고하여 사용했다.
• visit 배열의 세 번째 부분이 열쇠이다. 열쇠를 획득 할 때마다 다시 탐색하기 위해 사용해준다.
• key를 가지고 있는지 없는지를 판별하며 bfs를 돌다가, 1을 만나면 거리를 출력 해 준다.