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

< 풀이 >

 

너무 복잡하게 생각했는데, 그냥 BFS를 하는데 key를 가지고 있는 조건들을 비트마스킹하면 된다.

key를 획득한 정보나 움직인 횟수를 count하는 변수를 잘 관리해야 꼬이지 않는다..ㅠㅠ for문 체크할 때마다 초기화해줘야 하는데 잘못하면 중복해서 count되는 경우도 있고 그렇다. 

공간 복잡도는 A~F의 key만 가지고 있는 지 확인하면 되고, 전체 map이 50x50이니까 총 O(50*50*2^6)의 복잡도를 가진다. 

 

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

vector<string> miro;
vector<vector< vector<bool> > > visited(51, vector<vector<bool> >(51, vector<bool>(1<<8, false)));
int move_x[4] = {1, 0, 0, -1};
int move_y[4] = {0, 1, -1, 0};
int N, M; 

int bfs(){
    int x = 0;
    int y = 0;
    bool flag = false;
    for(;x<N;x++){
        y = 0;
        for(; y<M;y++){
            if (miro[x][y] == '0') {
                flag = true;
                break; // 시작 위치
            }
        }
        if (flag) break;
    }
    queue<pair<ii, ii> > q;
    q.push({{x, y}, {0, 0}});
    visited[x][y][0] = true;
    while(!q.empty()){
        auto item = q.front();
        q.pop();
        int a = item.first.first;
        int b = item.first.second;
        int key = item.second.first;
        int n_move = item.second.second;

        for(int i=0; i<4; i++){
            int new_x = a + move_x[i];
            int new_y = b + move_y[i];
            int new_key = key;

            // 진입 불가능한 케이스
            if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= M) continue;
            if (miro[new_x][new_y] == '#') continue;
            
            // key를 획득!
            if ('a' <= miro[new_x][new_y] && miro[new_x][new_y] <= 'f'){
                new_key |= (1 << (miro[new_x][new_y] - 'a' + 1));
            }
            
            // 방문 여부 확인
            if (visited[new_x][new_y][new_key]) continue;
            else {
                visited[new_x][new_y][new_key] = true;
                if ('A' <= miro[new_x][new_y] && miro[new_x][new_y] <= 'F'){ // 문
                    if ((new_key & (1 << (miro[new_x][new_y] - 'A' + 1))) == 0) continue; //열쇠 없으면 패스
                }
                q.push({{new_x, new_y}, {new_key, n_move+1}});

                if (miro[new_x][new_y] == '1') return n_move + 1;
            }
        }
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for(int i=0; i<N;i++){
        string temp; cin >> temp;
        miro.pb(temp);
    }
    cout << bfs() << '\n';
    return 0;
}