[백준] 9328 열쇠

어려웠던 문제다

대문자 A ~ Z는 문 // 소문자 a~z는 열쇠를 나타낸다

문을 열려면 열쇠가 필요하다

이 문제에서는 홈칠 수 있는 문서의 최대 개수를 구해야 한다

bfs를 돌리는데 문의 bfs를 따로 만들어 준다

그래서 내가 돌아 다니다가 열수 없는 문을 만난다면 문 bfs에 따로 넣어두고 그 문을 열어주는 열쇠를 만나면 문의 좌표를 다 내가 갈 수 있게 큐에 넣어준다!

헷갈리지만 풀면 이해가 간다

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int t, n, m;
char map[111][111];
bool check[111][111];
bool key[111];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
int main() {
    scanf(" %d", &t);
    while (t--) {
        memset(map, 0, sizeof(map));
        memset(check, 0, sizeof(check));
        memset(key, 0, sizeof(key));
        scanf(" %d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf(" %1c", &map[i][j]);
            }
        }
 
        string s; cin >> s;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '0') continue;
            key[s[i] - 'a'] = true;
        }
        int ans = 0;
        queue<pair<int, int>> q;
        queue<pair<int, int>> door[26];
        q.push({ 0,0 }); check[0][0] = true;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx <= n + 1 && 0 <= ny && ny <= m + 1) {
                    if (map[nx][ny] == '*' || check[nx][ny]) continue;
                    check[nx][ny] = true;
                    if ('A' <= map[nx][ny] && map[nx][ny] <= 'Z') {
                        if (key[map[nx][ny] - 'A']) q.push({ nx,ny });
                        else door[map[nx][ny] - 'A'].push({ nx,ny });
                    }
                    else if ('a' <= map[nx][ny] && map[nx][ny] <= 'z') {
                        q.push({ nx,ny });
                        if (!key[map[nx][ny] - 'a']) {
                            key[map[nx][ny] - 'a'] = true;
                            while (!door[map[nx][ny] - 'a'].empty()) {
                                q.push({ door[map[nx][ny] - 'a'].front() });
                                door[map[nx][ny] - 'a'].pop();
                            }
                        }
                    }
                    else {
                        q.push({ nx,ny });
                        if (map[nx][ny] == '$') ans++;
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
}