[Algorithm] Baekjoon 9328번 : 열쇠

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

9328번: 열쇠

struct Node
{
    int y;
    int x;
};
 
 
int t, h, w;
vector<string> arr;
int dir[4][2] = { {-1,0}, {1,0},{0,-1}, {0,1} };
map<char, bool> keys; // 키값 소문자
bool visited[101][101] = { false };
 
vector<Node> candidateNodes; // 더 탐색가능한 노드들을 담아둔다.
map<char,vector<Node>> lockedDoorNodes; // 잠긴문을 만나면 일단 무조건 넣는다. 키값 대문자
vector<int> answer;
int answerCount = 0;
 
 
void BFS()
{
    queue<Node> q;
 
    for (int i = 0; i < candidateNodes.size(); ++i)
    {
        q.push(candidateNodes[i]);
        visited[candidateNodes[i].y][candidateNodes[i].x] = true;
    }
 
    candidateNodes.clear();
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= h) continue;
            if (nextX < 0 || nextX >= w) continue;
            if (arr[nextY][nextX] == '*') continue;
            if (visited[nextY][nextX]) continue;
 
            // 빈공간 or 문 or 열쇠 or 문서
 
            if (arr[nextY][nextX] == '.')
            {
                visited[nextY][nextX] = true;
                q.push({ nextY,nextX });
            }
            else if (arr[nextY][nextX] >= 'A' && arr[nextY][nextX] <= 'Z') // 문이면
            {
                if (keys[arr[nextY][nextX] + 32]) // 키 있으면
                {
                    visited[nextY][nextX] = true;
                    q.push({ nextY,nextX });
                }
                else // 키 없으면 후보로 등록.
                {
                    visited[nextY][nextX] = true;
                    lockedDoorNodes[arr[nextY][nextX]].push_back({ nextY,nextX });
                }
            }
            else if (arr[nextY][nextX] >= 'a' && arr[nextY][nextX] <= 'z') // 열쇠면
            {
                visited[nextY][nextX] = true;
                keys[arr[nextY][nextX]] = true;
                q.push({ nextY,nextX });
            }
            else if (arr[nextY][nextX] == '$')
            {
                ++answerCount;
                visited[nextY][nextX] = true;
                q.push({ nextY,nextX });
            }
        }
    }
 
    // 여기서 locked검사해서 candidate넣어줄만한거 넣어주기.
 
    for (auto iter = lockedDoorNodes.begin(); iter != lockedDoorNodes.end(); ++iter)
    {
        int vSize = iter->second.size();
 
        for (int i = vSize-1; i >= 0; --i)
        {
            if (keys[iter->first + 32])
            {
                candidateNodes.push_back(iter->second[i]);
                iter->second.pop_back();
            }
        }
    }
 
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        memset(visited, false, sizeof(visited));
        candidateNodes.clear();
        arr.clear();
        keys.clear();
        lockedDoorNodes.clear();
        answerCount = 0;
 
        cin >> h >> w;
 
        for (int row = 0; row < h; ++row)
        {
            string temp;
            cin >> temp;
            arr.push_back(temp);
        }
 
        string keyInfo;
        cin >> keyInfo;
 
        if (keyInfo[0] != '0')
        {
            for (int j = 0; j < keyInfo.size(); ++j)
            {
                keys[keyInfo[j]] = true;
            }
        }
 
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                // 외곽 검사
 
                if (i == 0 || i == h - 1) // 맨 위 맨 아래
                {
                    if (arr[i][j] == '.')
                    {
                        candidateNodes.push_back({ i,j });
                    }
                    else if (arr[i][j] >= 'A' && arr[i][j] <= 'Z') // 문인데
                    {
                        if (keys[arr[i][j] + 32]) // 열쇠있으면
                        {
                            candidateNodes.push_back({ i,j });
                        }
                        else // 없으면 검사는 해야하니까 lock에 넣어놓고
                        {
                            lockedDoorNodes[arr[i][j]].push_back({ i,j });
                        }
                    }
                    else if (arr[i][j] >= 'a' && arr[i][j] <= 'z') // 열쇠면
                    {
                        keys[arr[i][j]] = true;
                        candidateNodes.push_back({ i,j });
                    }
                    else if (arr[i][j] == '$')
                    {
                        ++answerCount;
                        candidateNodes.push_back({ i,j });
                    }
                }
                else
                {
                    if (j == 0 || j == w - 1)
                    {
                        if (arr[i][j] == '.')
                        {
                            candidateNodes.push_back({ i,j });
                        }
                        else if (arr[i][j] >= 'A' && arr[i][j] <= 'Z') // 문인데
                        {
                            if (keys[arr[i][j] + 32]) // 열쇠있으면
                            {
                                candidateNodes.push_back({ i,j });
                            }
                            else // 없으면 검사는 해야하니까 lock에 넣어놓고
                            {
                                lockedDoorNodes[arr[i][j]].push_back({ i,j });
                            }
                        }
                        else if (arr[i][j] >= 'a' && arr[i][j] <= 'z') // 열쇠면
                        {
                            keys[arr[i][j]] = true;
                            candidateNodes.push_back({ i,j });
                        }
                        else if (arr[i][j] == '$')
                        {
                            ++answerCount;
                            candidateNodes.push_back({ i,j });
                        }
                    }
                }
 
            }
        }
 
        while (!candidateNodes.empty())
        {
            BFS();
        }
 
        answer.push_back(answerCount);
    }
 
    for (int i = 0; i < answer.size(); ++i)
    {
        cout << answer[i] << endl;
    }
}

 

조건이 많아서 그렇지, 사실 어렵지는 않은 문제.

특히 문제를 보자마자 예외케이스 몇개가 바로 생각나서 다행히 크게 고생은 안했다.

 

탐색전에 외각에서부터 시작해야하니, 진입가능한 노드들을 미리 구해서 candidateNodes.에 담아놓는다.

그리고 그걸 기반으로 BFS를 수행하며, 수행하는 도중 문을 만났을 때 열쇠가 있다면 그대로 탐색하면되고 문이 없다면 일단 lockedDoorNodes라는 곳에 보관한다. 

이후 메인BFS로직이 끝나고 나면, lockedDoorNodes를 순회하면서 잠긴문좌표노드에 대해 검사를 하는데, 해당 노드에대해 열쇠가 있다면 candidateNodes로 옮긴다.

즉 candidateNodes는 실제로 탐색시작가능한 노드들만 담는 곳이다.

 

이렇게 반복하다가 candidateNodes가 텅 비어버린다면, 더이상 탐색할 공간이 전혀 없다는 의미이니 해당 테스트케이스를 종료하면 된다.

 

헷갈리기 싫어서 모든 케이스에 대해 명시적으로 작성하다보니 코드가 좀 불필요하게 길긴 한데, 그렇다고 성능이 나쁜건 아니니 그냥 넘어가야겠다.