BOJ 1194 · 달이 차오른다, 가자.

알고리즘 분류 : BFS  

미로를 탈출하는데 걸리는 최단 거리를 구하는 문제다. 전형적인 BFS 문제인데, 열쇠 조건이 약간 까다롭다. 열쇠는 소문자 a~f로 총 6가지 종류가 있으며, 문도 마찬가지로 대문자 A~F 6종류가 있다. 열쇠가 없으면 해당 알파벳에 상응하는 문을 열 수 없어서 통과할 수 없다. 열쇠 조건을 만족하면서 방문 여부를 체크하기 위해 3차원 배열을 선언할 필요가 있다.

• 방문 여부 체크와 이동 거리를 저장할 배열 'dist'를 3차원으로 선언한다.
• dist 배열의 인덱스는 [x좌표] [y좌표] [보유 열쇠] 이다.
• 보유 열쇠는 비트마스크를 사용한다.
• 각 열쇠는 a(1<<0), b(1<<1), c(1<<2), d(1<<3), e(1<<4), f(1<<5) 이다.
• 예를 들어 a, c, f 열쇠를 가졌다면, 100101로 나타낼 수 있다. 10진수로 나타내면 37이다.
• 모든 열쇠를 가졌다면, 111111이다. 10진수로 나타내면 63이므로, [보유 열쇠] 인덱스는 64 사이즈로 해야 한다.
• 열쇠 칸(a~f)에 방문하면, OR 연산을 통해 해당 열쇠를 얻는다.
• 문 칸(A~F)에 방문하면, AND 연산을 통해 해당 열쇠가 있는지 확인하고, 없으면 통과하지 못하게 한다.
• 벽 칸('#')은 항상 통과하지 못하며, 빈 곳('.')은 항상 통과할 수 있다.
• 출구('1')는 여러 개일 수도 있으며, 어느 곳이든 출구에 도착하면 바로 BFS를 종료한다.

---

C++ 소스코드

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

struct maze {
    int x, y, k;
};

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

void bfs() {
    queue<maze> q;
    q.push({sx, sy, 0});
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, k = q.front().k; q.pop();
        if (a[x][y]== '1') {
            printf("%d\n", dist[x][y][k]);
            return;
        }
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i], nk = k;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            char next = a[nx][ny];
            if ('a' <= next && next <= 'f') nk |= (1<<(next-'a'));
            else if ('A' <= next && next <= 'F') {
                if (!(nk & (1<<(next-'A')))) continue;
            }
            if (dist[nx][ny][nk] || next == '#') continue;
            q.push({nx, ny, nk});
            dist[nx][ny][nk] = dist[x][y][k] + 1;
        }
    }
    printf("-1\n");
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            scanf(" %1c", &a[i][j]);
            if (a[i][j] == '0') sx = i, sy = j;
        }
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
dist = [[[0]*64 for _ in range(m)] for _ in range(n)]
q = deque()

def init():
    for i in range(n):
        for j in range(m):
            if a[i][j] == '0':
                q.append((i, j, 0))
                return

def bfs():
    while q:
        x, y, k = q.popleft()
        if a[x][y] == '1':
            print(dist[x][y][k])
            return
        for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
            nx, ny, nk = x+dx, y+dy, k
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            c = a[nx][ny]
            if c.islower():
                nk |= (1<<(ord(c)-ord('a')))
            elif c.isupper() and not nk & (1<<(ord(c)-ord('A'))):
                continue
            if not dist[nx][ny][nk] and c != '#':
                q.append((nx, ny, nk))
                dist[nx][ny][nk] = dist[x][y][k] + 1
    print(-1)

init()
bfs()

---

참고

• 백준 온라인 저지 : BOJ 1194