백준 9328번 [열쇠](C++) -yes6686- 티스토리

백준 문제 풀이: 9328 (열쇠)

---

문제 링크: https://www.acmicpc.net/problem/9328

문제 설명:

감옥에 숨겨진 문서($)를 훔치기 위해 빌딩에 침입하려고 합니다. 빌딩은 벽(*), 빈 공간(.), 문서($), 문(A~Z), 열쇠(a~z)로 구성되어 있고, 바깥쪽에서 시작하여 내부로 진입하며 열쇠를 수집해 문을 열 수 있습니다. 초기 열쇠 목록이 주어지고, 주어진 보드에서 얻을 수 있는 문서의 최대 개수를 구하는 문제입니다.

BFS와 키-문 매핑 로직을 이용하여 시뮬레이션을 구현해야 하며, 바깥 경계에서 진입 가능한 모든 지점을 탐색하는 것이 핵심입니다.

---

문제 해결 코드

// 열쇠 (BFS 기반 시뮬레이션)
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

char arr[101][101];
int visited[101][101];
int key[27];  // a~z 소문자 열쇠 상태
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int h, w;

vector<pair<int, int>> v;  // 열쇠가 없어 잠시 보류한 문 위치
queue<pair<int, int>> q;
int ans = 0;

void bfs(int x, int y) {
    q.push({ x, y });
    visited[x][y] = 1;

    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
            if (visited[nx][ny] || arr[nx][ny] == '*') continue;

            visited[nx][ny] = 1;

            if (arr[nx][ny] >= 'A' && arr[nx][ny] <= 'Z') {
                if (key[arr[nx][ny] - 'A']) {
                    q.push({ nx, ny });
                } else {
                    v.push_back({ nx, ny });
                }
            } else if (arr[nx][ny] >= 'a' && arr[nx][ny] <= 'z') {
                key[arr[nx][ny] - 'a'] = 1;
                q.push({ nx, ny });
            } else if (arr[nx][ny] == '$') {
                ans++;
                q.push({ nx, ny });
            } else {
                q.push({ nx, ny });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        cin >> h >> w;
        ans = 0;

        for (int i = 0; i < h; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < s.size(); j++) {
                arr[i][j] = s[j];
            }
        }

        string keys;
        cin >> keys;
        if (keys[0] != '0') {
            for (char c : keys) {
                key[c - 'a'] = 1;
            }
        }

        // 외곽 탐색 (출입구 후보)
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i == 0 || j == 0 || i == h - 1 || j == w - 1) {
                    if (!visited[i][j]) {
                        if (arr[i][j] == '.') {
                            bfs(i, j);
                        } else if (arr[i][j] >= 'a' && arr[i][j] <= 'z') {
                            key[arr[i][j] - 'a'] = 1;
                            bfs(i, j);
                        } else if (arr[i][j] >= 'A' && arr[i][j] <= 'Z') {
                            if (key[arr[i][j] - 'A']) {
                                bfs(i, j);
                            } else {
                                v.push_back({ i, j });
                            }
                        } else if (arr[i][j] == '$') {
                            ans++;
                            bfs(i, j);
                        }
                    }
                }
            }
        }

        // 열쇠가 생겨 다시 접근 가능한 문 탐색
        while (true) {
            int found = 0;
            for (int i = 0; i < v.size(); i++) {
                int x = v[i].first;
                int y = v[i].second;
                if (x == -1 && y == -1) continue;

                if (key[arr[x][y] - 'A']) {
                    v[i] = { -1, -1 };  // 처리됨
                    bfs(x, y);
                    found = 1;
                }
            }
            if (!found) break;
        }

        cout << ans << '\n';

        // 초기화
        memset(key, 0, sizeof(key));
        memset(visited, 0, sizeof(visited));
        v.clear();
        while (!q.empty()) q.pop();
    }
}

---

코드 설명

• 핵심 알고리즘: BFS를 사용하여 외곽에서 탐색을 시작하며, 열쇠를 얻을 때마다 방문하지 못했던 문의 위치를 다시 탐색하는 반복 구조입니다.
• 구현 세부사항: 열쇠가 없으면 문의 위치를 v에 저장해두었다가, 나중에 해당 열쇠를 얻으면 다시 BFS를 통해 방문합니다.
• 시간 복잡도 분석: O(h ⋅ w), 각 칸은 한 번씩만 방문하므로 BFS 기반 탐색이 효율적으로 작동합니다.

---

결과

각 테스트 케이스마다 얻을 수 있는 문서의 개수를 한 줄씩 출력합니다.

예시 입력:

1
5 5
*B*.*
.$a$.
*bAb*
.$.$.
*.*.*
0

예시 출력:

4

다른 접근 방식이나 개선 아이디어가 있다면 댓글로 공유 부탁드립니다!