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

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

 

www.acmicpc.net

풀이

이 문제에서는 열쇠를 보유하고 있는 상태를 표시하는 것이 관건인 문제이다. 열쇠 보유 상태를 표현하기 쉽게 하기 위해서 비트 마스킹을 사용했다.

a 열쇠를 집은 경우 000001 으로 표기한다.
b 열쇠를 집은 경우 000010 으로 표기한다.
c 열쇠를 집은 경우 000100 으로 표기한다.
d 열쇠를 집은 경우 001000 으로 표기한다.
e 열쇠를 집은 경우 010000 으로 표기한다.
f 열쇠를 집은 경우 100000 으로 표기한다.

비트 마스킹을 사용하면 여러개의 키를 가지고 있는 경우도 쉽게 표현할 수 있다. 그리고 열쇠를 가지고 있는 경우에 따라서 갈 수 있는 경로가 달라지기 때문에 중복 체크하는 배열을 3차원으로 구성해서 해결하였다. 이 때 모든 열쇠를 가지고 있는 경우 111111이므로 최대 64까지 배열을 구성해서 visited[50][50][64]로 선언해서 해결하였다.

코드

#include <iostream>
#include <queue>
using namespace std;

struct minsik {
    int x, y, key, cnt;
};

int n, m, sx, sy;
char map[50][50];
bool visited[50][50][64];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

// 열쇠를 가지고 있는지 확인
bool check_key(int cur_key, char door) {
    if ((cur_key & (1 << (door - 'A'))) == 0) return false;
    return true;
}

// 열쇠를 집으면 실행
int set_key(int cur_key, char value) {
    return cur_key | (1 << (value - 'a'));
}

int bfs() {
    queue<minsik> q;
    q.push({ sx, sy, 0, 0 });
    visited[sy][sx][0] = true;

    while (!q.empty()) {
        minsik cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i]; int ny = cur.y + dy[i];
            if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1 || visited[ny][nx][cur.key] || map[ny][nx] == '#') continue;
            // 문을 만난 경우
            if ('A' <= map[ny][nx] && map[ny][nx] <= 'F') {
                // 해당 문에 맞는 열쇠가 있는지 확인
                if (check_key(cur.key, map[ny][nx])) {
                    q.push({ nx, ny, cur.key, cur.cnt + 1 });
                    visited[ny][nx][cur.key] = true;
                }
            }
            // 열쇠를 집는 경우
            else if ('a' <= map[ny][nx] && map[ny][nx] <= 'f') {
                int key = set_key(cur.key, map[ny][nx]);
                q.push({ nx, ny, key, cur.cnt + 1 });
                visited[ny][nx][key] = true;
            }
            // 목적지에 도착한 경우
            else if (map[ny][nx] == '1') return cur.cnt + 1;
            else {
                q.push({ nx, ny, cur.key, cur.cnt + 1 });
                visited[ny][nx][cur.key] = true;
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == '0') {
                sx = j; sy = i;
            }
        }
    cout << bfs() << '\n';
    return 0;
}