[BOJ] 백준 9328 열쇠

문제 링크

www.acmicpc.net/problem/9328

9328번: 열쇠

 

풀이

범위가 작아 무슨 짓을 해도 풀 수 있습니다.

1) 저는 bfs를 여러 번 돌려서 풀었는데, 매번 시작할 수 있는 시작점에서 출발해 갈 수 있는 데까지 가줍니다. 이 시작점은 현재 갖고 있는 열쇠 현황에 따라 달라지기 때문에 매번 새로 구해주어야 합니다.

2) 탐색 중 열쇠를 먹었다면 업데이트하고, 그 열쇠로 열 수 있는 문은 다음번 bfs에서 통과할 수 있게 됩니다.

 

이런 방식으로 더이상 서류나 열쇠를 먹을 수 없을 때까지 돌려 정답을 구해주면 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define ft first
#define sd second
using namespace std;
using pii = pair<int, int>;

string p[111];
int n, m;
bool key[26], chk[111][111];
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool isValid(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        memset(key, 0, sizeof(key));
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }
        string s;
        cin >> s;
        for (char c: s) {
            if (c == '0') continue;
            key[c - 'a'] = true;
        }

        bool c = true;
        int ans = 0;
        while (c) {
            queue<pii> q;
            memset(chk, 0, sizeof(chk));
            auto foo = [&](char c) {
                if (c == '*') return false;
                if (isupper(c) && !key[c - 'A']) return false;
                if (islower(c)) key[c - 'a'] = true;
                return true;
            };
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if ((i == 0 || i == n - 1 || j == 0 || j == m - 1) && foo(p[i][j])) {
                        q.emplace(i, j);
                        chk[i][j] = true;
                    }
                }
            }
            c = false;
            while (!q.empty()) {
                auto[x, y] = q.front();
                q.pop();
                char now = p[x][y];
                if (isupper(now)) {
                    if (!key[now - 'A']) continue;
                    p[x][y] = '.';
                }
                if (islower(now)) {
                    c = true;
                    key[now - 'a'] = true;
                    p[x][y] = '.';
                }
                if (now == '$') {
                    ans++;
                    c = true;
                    p[x][y] = '.';
                }
                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (!isValid(nx, ny) || chk[nx][ny] || p[nx][ny] == '*') continue;
                    chk[nx][ny] = true;
                    q.emplace(nx, ny);
                }
            }
        }
        cout << ans << '\n';
    }
}