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

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct node{
    int y, x, move, key;
    node(int y, int x, int move, int key){
        this->y = y;
        this->x = x;
        this->move = move;
        this->key = key;
    }
};

int n, m;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
map<tuple<int, int, int>, int> visited;
vector<vector<char>> maze;
queue<node> q;

int bfs(){
    while(!q.empty()){
        int y = q.front().y;
        int x = q.front().x;
        int move = q.front().move;
        int key = q.front().key;
        q.pop();
        if(maze[y][x] == '1') return move;
        for(int j = 0; j < 4; j++){
            int ny = y+dy[j];
            int nx = x+dx[j];
            if(0 <= ny && ny < n && 0 <= nx && nx < m && !visited[make_tuple(key, ny, nx)]){
                int nextKey = key;
                int ascii = (int)maze[ny][nx];
                if(0x61 <= ascii && ascii <= 0x7a){
                    nextKey |= (1<<(ascii-0x61));
                    visited[make_tuple(nextKey, ny, nx)] = 1;
                    q.push(node(ny, nx, move+1, nextKey));
                }
                else if(0x41 <= ascii && ascii <= 0x5a){
                    if(key&(1<<(ascii-0x41))){
                        visited[make_tuple(key, ny, nx)] = 1;
                        q.push(node(ny, nx, move+1, key));
                    }
                }
                else if(maze[ny][nx] != '#'){
                    visited[make_tuple(key, ny, nx)] = 1;
                    q.push(node(ny, nx, move+1, key));
                }
            }
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    maze.resize(n, vector<char>(m));
    for(int y = 0; y < n; y++){
        for(int x = 0; x < m; x++){
            cin >> maze[y][x];
            if(maze[y][x] == '0'){
                q.push(node(y, x, 0, 0));
                visited[make_tuple(0, y, x)] = 1;
            }
        }
    }
    cout << bfs();
    return 0;
}

며칠 전 백조의 호수 문제를 풀었던 기억을 되살려 호수의 얼음이 조금씩 녹듯이, 열쇠를 찾을 때 마다 이동할 수 있는 미로의 범위를 늘려 나가는 식으로 풀이하려 했지만 반례가 너무나 많았다. 현재까지 발견한 열쇠를 비트마스킹 기법을 적용해 정수형태로 관리하고 bfs 를 보유중인 열쇠와 방문한 좌표를 상태로 하는 방문 배열을 사용하여 진행시키면 된다.