백준 1194번 달이 차오른다, 가자. - C++ 풀이

---

 

1. 열쇠 소지 현황을 비트 마스크 keys로 나타낸다.
2. (r, c) 위치에서 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다.
3. BFS로 탈출 상황까지 가는 최단 이동 횟수를 구한다.

 

1. 열쇠 소지 현황을 비트마스크 keys로 나타낸다.

 BFS에서 방문 여부를 배열로 기록하기 쉽게 하기 위해서 열쇠 소지 현황을 비트 마스크를 이용해서 나타내 준다.

 

2. (r, c) 위치에서 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다.

 어떠한 상황을 나타내는 데 필요한 값은 위치와 열쇠 소지 현황이다. (r, c) 위치에서 비트 마스크로 나타낸 keys 열쇠들을 가지고 있는 상황은 {r, c, keys}로 나타낼 수 있다.

 

3. BFS로 탈출 상황까지 가는 최단 이동 횟수를 구한다.

 각 상황을 그래프의 노드로 생각하면, BFS를 이용해서 시작 위치에서 열쇠를 아무것도 가지고 있지 않은 상황에서, 탈출 위치에 도착하는 상황까지의 최단 이동 횟수를 구할 수 있다. 방문 여부 표시를 위한 visit 배열은 visit[r][c][keys] 형태로 운영하면 된다.

반응형

---

#include <iostream>
#include <queue>

using namespace std;

int N, M, sr, sc;
string board[51];
bool visit[51][51][1<<6];

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

struct Node {
    int r, c, keys;
};

int solution() {
    queue<pair<int, Node>> q;
    visit[sr][sc][0] = true;
    q.push({0, {sr, sc, 0}});
    
    while (!q.empty()) {
        int d = q.front().first;
        Node node = q.front().second;
        q.pop();
        
        for (int i=0; i<4; i++) {
            int nr = node.r + dr[i];
            int nc = node.c + dc[i];
            int x, nkeys;
            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            
            switch (board[nr][nc]) {
                case '.': case '0': 
                    if (!visit[nr][nc][node.keys]) {
                        visit[nr][nc][node.keys] = true;
                        q.push({d+1, {nr, nc, node.keys}});
                    }
                    break;
                case '#': break;
                case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
                    x = board[nr][nc] - 'a';
                    nkeys = node.keys | (1 << x);
                    if (!visit[nr][nc][nkeys]) {
                        visit[nr][nc][nkeys] = true;
                        q.push({d+1, {nr, nc, nkeys}});
                    }
                    break;
                case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
                    x = board[nr][nc] - 'A';
                    if ((node.keys & (1 << x)) != 0 && !visit[nr][nc][node.keys]) {
                        visit[nr][nc][node.keys] = true;
                        q.push({d+1, {nr, nc, node.keys}});
                    }
                    break;
                case '1': return d+1;
            }
        }
    }
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        cin >> board[i];
        for (int j=0; j<M; j++) {
            if (board[i][j] == '0') {
                sr = i;
                sc = j;
            }
        }
    }
    
    cout << solution();    

    return 0;
}