[ 백준 BOJ ] 9328 번 - 열쇠 (C++)

https://www.acmicpc.net/problem/9328

9328번: 열쇠

알고리즘 분류에 구현이 있으면 코딩 하는 거 자체가 너무 귀찮은 거 같다..

bfs를 이용하는 문제로, 이중 for문으로 방문하지 않은 곳을 방문해주면 된다. 이 때 이중 for문에서 열쇠를 얻었다 한들 이미 탐색이 끝났을 수도 있으므로 무한 루프로 계속 반복해준다. 키의 개수나 문서의 개수가 달라지지 않고 똑같으면 무한 루프를 벗어나면 된다. 주의할 점으로는 이중 for문으로 방문하지 않은 곳을 방문하므로 해당 장소를 실질적으로 도달할 수 있는지를 봐야한다. 따라서 상하좌우에 방문한 곳이 있는지 따져봐야한다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <queue>

#define endl '\n'
#define ll long long
#define pii pair<int, int>

using namespace std;

int moveX[4] = {1, -1, 0, 0};
int moveY[4] = {0, 0, 1, -1};

int h, w;
string m[100];
bool checked[100][100];
bool alpha[91];
int ans;
int keyNum;

void bfs(int i, int j)
{
    queue<pii> q;
    q.emplace(i, j);
    while (!q.empty())
    {
        pii node = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nodeY = node.first + moveY[i];
            int nodeX = node.second + moveX[i];
            if (nodeY >= 0 && nodeY < h && nodeX >= 0 && nodeX < w)
            {
                if ('A' <= m[nodeY][nodeX] && m[nodeY][nodeX] <= 'Z')
                {
                    if (alpha[m[nodeY][nodeX]] && !checked[nodeY][nodeX])
                    {
                        checked[nodeY][nodeX] = true;
                        q.emplace(nodeY, nodeX);
                    }
                }
                else if (m[nodeY][nodeX] == '.' && !checked[nodeY][nodeX])
                {
                    checked[nodeY][nodeX] = true;
                    q.emplace(nodeY, nodeX);
                }
                else if (m[nodeY][nodeX] == '$' && !checked[nodeY][nodeX])
                {
                    q.emplace(nodeY, nodeX);
                    checked[nodeY][nodeX] = true;
                    ans++;
                }
                else if ('a' <= m[nodeY][nodeX] && m[nodeY][nodeX] <= 'z')
                {
                    if (!checked[nodeY][nodeX])
                    {
                        alpha[m[nodeY][nodeX] - 32] = true;
                        keyNum++;
                        checked[nodeY][nodeX] = true;
                        q.emplace(nodeY, nodeX);
                    }
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> h >> w;
        string keyList;
        memset(checked, false, sizeof(checked));
        memset(alpha, false, sizeof(alpha));
        for (int i = 0; i < h; i++)
        {
            cin >> m[i];
        }
        cin >> keyList;
        for (int i = 0; i < keyList.size(); i++)
        {
            if (keyList[i] != '0')
            {
                alpha[keyList[i] - 32] = true;
                keyNum++;
            }
        }
        while (true)
        {
            int k = keyNum;
            int a = ans;
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    if (checked[i][j])
                        continue;
                    if (m[i][j] == '*')
                        continue;
                    if ('A' <= m[i][j] && m[i][j] <= 'Z')
                    {
                        if (!alpha[m[i][j]])
                            continue;
                    }
                    bool isOut = false;
                    if (i == 0 || i == h - 1 || j == 0 || j == w - 1)
                    {
                        isOut = true;
                    }
                    else
                    {
                        for (int m = 0; m < 4; m++)
                        {
                            int my = i + moveY[m];
                            int mx = j + moveX[m];
                            if (my >= 0 && my < h && mx >= 0 && mx < w)
                            {
                                if (checked[my][mx])
                                {
                                    isOut = true;
                                    break;
                                }
                            }
                        }
                    }
                    if (!isOut)
                        continue;
                    if ('a' <= m[i][j] && m[i][j] <= 'z')
                    {
                        alpha[m[i][j] - 32] = true;
                        keyNum++;
                    }
                    if (m[i][j] == '$')
                    {
                        ans++;
                    }
                    checked[i][j] = true;
                    bfs(i, j);
                }
            }
            if (k == keyNum && a == ans)
            {
                break;
            }
        }
        cout << ans << endl;
        ans = 0;
        keyNum = 0;
    }
    return 0;
}