BOJ 9328 · 열쇠

알고리즘 분류 : BFS  

BFS를 통해 맵을 탐색하면서 문서를 얻는 문제다. 이동 가능한 위치까지 최대한 이동해서 문서를 얻어야 한다. 빌딩 밖을 나갔다가 다시 들어와서 문을 열 수 있으므로, 주어진 맵을 확장할 필요가 있다. 예를 들면 아래 그림처럼 확장한다.

• 맵을 입력받을 때, 가장자리를 빈 공간(.)으로 만든다. 맵의 범위가 가로(1~W), 세로(1~H)라면, 가로(0, W+1), 세로(0, H+1)를 빈 공간으로 설정하면 된다. C++ 코드에서는 빈 공간을 0으로 처리했다.
• 열쇠를 저장할 26(알파벳 총 개수) 길이의 배열을 만들고, 열쇠가 있으면 true, 없으면 false로 처리한다.
• 큐는 총 2가지 종류이다. 이동 위치를 나타낼 Position queue와, 문의 위치를 나타낼 Door queue이다. Door queue는 열쇠와 마찬가지로 26개이다.
• 출발은 (0, 0)으로, 빌딩 밖에서 시작한다.
• 맵을 이동하면서 범위를 벗어나거나, 벽(*)을 만나면 무시한다.
• 맵을 이동하면서 문(A~Z)을 만나면, 해당 문의 위치를 Door queue에 집어 넣는다. 
• 맵을 이동하면서 열쇠(a~z)를 만나면, 해당 열쇠를 true로 한다. 그리고 Door queue의 해당 문자에 대한 모든 값을 pop하여 Position queue에 집어 넣는다. 
• 맵을 이동하면서 문서($)를 만나면, 이를 카운트한다.
• 테스트 케이스가 여러 번 있으므로, 데이터 초기화를 잊지 말아야 한다.

---

C++ 소스코드

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

struct map {
    int x, y;
};

int h, w;
char a[102][102];
bool check[102][102];
bool key[26];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void input() {
    memset(a, 0, sizeof(a));
    memset(key, false, sizeof(key));
    memset(check, false, sizeof(check));
    scanf("%d %d", &h, &w);
    for (int i=1; i<=h; i++) {
        for (int j=1; j<=w; j++) {
            char temp;
            scanf("%1s", &temp);
            if (temp != '.') a[i][j] = temp;
        }
    }
    char k[26];
    scanf("%s", k);
    for (int i=0; i<(int)strlen(k); i++) {
        if (k[i] == '0') break;
        key[k[i]-'a'] = true;
    }
}

int bfs() {
    queue<map> q;
    queue<map> dq[26];
    q.push({0, 0});
    check[0][0] = true;
    int ans = 0;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y;
        q.pop();
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx > h+1 || ny < 0 || ny > w+1) continue;
            if (a[nx][ny] == '*' || check[nx][ny]) continue;
            check[nx][ny] = true;
            if (a[nx][ny] == '$') {
                ans++;
            } else if ('A' <= a[nx][ny] && a[nx][ny] <= 'Z') {
                int k = a[nx][ny] - 'A';
                if (key[k] == false) {
                    dq[k].push({nx, ny});
                    continue;
                }
            } else if ('a' <= a[nx][ny] && a[nx][ny] <= 'z') {
                int k = a[nx][ny] - 'a';
                key[k] = true;
                while (!dq[k].empty()) {
                    int kx = dq[k].front().x, ky = dq[k].front().y;
                    dq[k].pop();
                    q.push({kx, ky});
                }
            }
            q.push({nx, ny});
        }
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        input();
        printf("%d\n", bfs());
    }
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

for _ in range(int(input())):
    h, w = map(int, input().split())
    a = [['.']+list(input().strip())+['.'] for _ in range(h)]
    a = ['.'*(w+2)] + a + ['.'*(w+2)]
    check = [[False]*(w+2) for _ in range(h+2)]
    keys = [False]*26
    k = input().strip()
    if k != '0':
        for t in k:
            keys[ord(t)-ord('a')] = True

    def bfs():
        q = deque()
        dq = [deque() for _ in range(26)]
        q.append((0, 0))
        check[0][0] = True
        ans = 0
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if nx < 0 or nx > h+1 or ny < 0 or ny > w+1:
                    continue
                if a[nx][ny] == '*' or check[nx][ny]:
                    continue
                check[nx][ny] = True
                if a[nx][ny] == '$':
                    ans += 1
                elif 'A' <= a[nx][ny] <= 'Z':
                    door = ord(a[nx][ny]) - ord('A')
                    if keys[door] is False:
                        dq[door].append((nx, ny))
                        continue
                elif 'a' <= a[nx][ny] <= 'z':
                    key = ord(a[nx][ny]) - ord('a')
                    keys[key] = True
                    while dq[key]:
                        kx, ky = dq[key].popleft()
                        q.append((kx, ky))
                q.append((nx, ny))
        return ans

    print(bfs())

---

참고

• 백준 온라인 저지 : BOJ 9328