[백준 1194번] [BFS / 비트마스킹] 달이 차오른다, 가자.

Approach

문제에서 이동 횟수의 최솟값을 묻는 상황이므로, BFS를 바로 떠올려주면 된다.

다만, 이 문제에서 되게 독특한 지점은 각 이동하는 상황에서 키를 가지고 있는지 여부가 굉장히 중요하다. 따라서 키를 가지고 있는지 여부를 set으로 넘겨줘도 되지만, 비트마스킹을 활용해주면 숫자 하나로 모든 것을 판단할 수 있게 된다.

 

추가적으로 visited도 신경써야 하는데, 키가 달라진다면 기존에 방문했던 곳이라도 양상이 달라질 수 있기 때문에 visited를 3차원으로 잡아주면 된다. 다음 문제와 비슷하게 느낌을 받았으면 충분하다. (위 문제도 단순히 같은 위치를 방문한다고 해서 같은 의미는 아니므로 차원을 1개 늘렸다.)

https://viyoung.tistory.com/334

[백준 2206번] [BFS] 벽 부수고 이동하기

 

추가적으로 구현 과정에서 UTF-8의 성질을 이용하면 조금 더 쉽게 키와 문을 매핑지을 수 있다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
int n, m;
pii start_point;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
char r[50][50];
bool visited[50][50][1 << 6];

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    set<pii> end_point;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> r[i][j];
            if(r[i][j] == '0'){
                start_point = make_pair(i, j);
            }
            else if(r[i][j] == '1'){
                end_point.insert(make_pair(i, j));
            }
        }
    }

    queue<piii> q;
    q.push(make_pair(start_point, 0));
    visited[start_point.first][start_point.second][0] = 1;
    int move_num = 0;
    while(!q.empty()){
        int q_size = q.size();
        for(int i = 0; i < q_size; i++){
            int x = q.front().first.first;
            int y = q.front().first.second;
            int key = q.front().second;
            if(end_point.find(q.front().first) != end_point.end()){
                cout << move_num << "\n";
                return 0;
            }
            q.pop();
            for(int j = 0; j < 4; j++){
                int dx = x + move_x[j];
                int dy = y + move_y[j];
                if(dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
                else{
                    if(!visited[dx][dy][key]){
                        if(r[dx][dy] == '.' || r[dx][dy] == '1' || r[dx][dy] == '0'){
                            q.push(make_pair(make_pair(dx, dy), key));
                            visited[dx][dy][key] = 1;
                        }
                        else if(r[dx][dy] == '#') continue;
                        else if (r[dx][dy] >= 'a' && r[dx][dy] <= 'f'){
                            int to = key | (1 << (r[dx][dy] - 'a'));
                            q.push(make_pair(make_pair(dx, dy), to));
                            visited[dx][dy][to] = 1;
                        }
                        else if(r[dx][dy] >= 'A' && r[dx][dy] <= 'F'){
                            if(key & (1 << (r[dx][dy] - 'A'))){
                                q.push(make_pair(make_pair(dx, dy), key));
                                visited[dx][dy][key] = 1;
                            }
                        }

                    }
                }
            }
        }
        move_num++;
    }

    cout << -1 << "\n";
    return 0;
}