[C++] 백준 9328 열쇠

#include <iostream>
#include <string.h>
#include <string>
#include <queue>
 
int h = 0;
int w = 0;
int ans = 0;
char Floor[102][102] = {};
bool visit[102][102] = {};
bool key[26] = {};
 
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
std::string alreadyKey = {};
 
void BFS(int row, int col)
{
    std::queue<std::pair<int, int>> que = {};
    std::queue<std::pair<int, int>> door[26] = {};
    que.push({ row, col });
    visit[row][col] = true;
 
    while (!que.empty())
    {
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
 
            if (nextX >= 0 && nextY >= 0 && nextX <= h + 1 && nextY <= w + 1)
            {
                if (Floor[nextX][nextY] == '*' || visit[nextX][nextY]) 
                    continue;
 
                visit[nextX][nextY] = true;
 
                if ('A' <= Floor[nextX][nextY] && Floor[nextX][nextY] <= 'Z')
                {
                    if (key[Floor[nextX][nextY] - 'A'])
                    {
                        que.push({ nextX, nextY });
                    }
 
                    else
                    {
                        door[Floor[nextX][nextY] - 'A'].push({ nextX, nextY });
                    }
                }
 
                else if ('a' <= Floor[nextX][nextY] && Floor[nextX][nextY] <= 'z')
                {
                    que.push({ nextX, nextY });
 
                    if (!key[Floor[nextX][nextY] - 'a'])
                    {
                        key[Floor[nextX][nextY] - 'a'] = true;
 
                        while (!door[Floor[nextX][nextY] - 'a'].empty())
                        {
                            que.push(door[Floor[nextX][nextY] - 'a'].front());
                            door[Floor[nextX][nextY] - 'a'].pop();
                        }
                    }
                }
 
                else
                {
                    que.push({ nextX, nextY });
 
                    if (Floor[nextX][nextY] == '$') 
                        ++ans;
                }
            }
        }
    }
}
 
int main(void)
{
    int t = 0;
    std::cin >> t;
 
    while (t--)
    {
        memset(Floor, 0, sizeof(Floor));
        memset(visit, false, sizeof(visit));
        memset(key, false, sizeof(key));
        alreadyKey.clear();
        ans = 0;
 
        std::cin >> h >> w;
 
        for (int i = 1; i <= h; ++i)
        {
            for (int j = 1; j <= w; ++j)
            {
                std::cin >> Floor[i][j];
            }
        }
 
        std::cin >> alreadyKey;
 
        for (int i = 0; i < alreadyKey.size(); ++i)
        {
            if (alreadyKey[i] == '0')
                continue;
 
            key[alreadyKey[i] - 'a'] = true;
        }
 
        BFS(0, 0);
 
        std::cout << ans << "\n";
    }
 
    return 0;
}
 

 

변형적인 넓이탐색 문제입니다.

1. 무조건 바깥에서 들어갈 수 있습니다 > 칸 수를 하나 더 늘려서 0,0에서 BFS를 시작하면 모든 바깥쪽에서 입장이 가능

2. 열쇠가 있어야 들어갈 수 있습니다 > 문을 만났을 경우 열쇠가 없다면 기존 큐가 아닌 새로운 큐에 저장해놓고 열쇠를 찾았을 경우 새로운 큐에 있는 위치를 기존 큐에 입력합니다. > 열쇠가 있든 없든 위치를 기억해놓고 푸는 겁니다.