달이 차오른다. 가자.

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

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

 

 

#include<iostream>
#include<queue>
#include<utility>
 
 
using namespace std;
 
int n, m, sx, sy;
string map[50];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int dist[50][50][64];
 
void bfs(int x,int y) {
    queue <pair<pair<int, int>, int> >q;
    q.push({ {x,y},0 });
    while (!q.empty()) {
        x = q.front().first.first; y = q.front().first.second;
        int cnt = q.front().second; q.pop();
        if (map[x][y] == '1') {
            cout << dist[x][y][cnt] << '\n';
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            int nc = cnt;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            char value = map[nx][ny];
            if ('a' <= value && value <= 'f') 
                nc |= (1 << (value - 'a'));
            else if ('A' <= value && value <= 'F') {
                if ((nc & (1 << (value - 'A'))) == false) continue;
            }
            if (dist[nx][ny][nc] || value == '#') continue;
            q.push({ {nx, ny},nc });
            dist[nx][ny][nc] = dist[x][y][cnt] + 1;
        }
    }
    cout << -1 << '\n';
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == '0') {
                sx = i; sy = j;
                break;
            }
        }
    }
    bfs(sx, sy);
    return 0;
 
}

유형이 익숙해진건지 아닌지는 모르겠다.

BFS문제중에서도 까다로운 유형인데, 사실 처음 보면 DFS가 더편해보이기도하는 문제다.

문제를 풀었던 요점은 다른게아니라 비트연산이다.

비트연산을 통해 a ~ f를 2진수 비트로 나타내서 or연산을 통하면 어떠한 열쇠를 가지고있는지 확인할수있고, 그에 따라 새로운 int 배열을 통해 문제를 풀어나갈수있다.