[Algorithm/C++17] 백준 9328 열쇠

문제

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

9328번: 열쇠

풀이 방법

2차원 공간을 탐색하면서 문서 몇 개를 훔칠 수 있을까를 계산하는 문제다.

이 문제만의 특이한 점은 다음과 같다.

• 처음 시작점이 정해져 있지 않고 주어진 2차원 공간 밖 아무데서나 시작할 수 있다. 
• 열쇠를 얻으면 그에 알맞는 문을 열고 지나갈 수 있다. 열쇠는 알파벳 a~z까지 있으므로 총 26개다.

첫 번째는 주어진 2차원 공간 밖의 테두리를 빈 공간으로 만들어준다. 크기를 h+2, w+2로 선언해주는 것이다. 이렇게 하고나서 (0, 0)부터 BFS로 탐색을 시작하면 해결된다. 

 

두 번째는 열쇠를 얻었을 때 문을 제거해주거나, 문을 탐색할 때 열쇠 소지 여부를 판단하고 지나가게 하면 된다. 조심해야 할 것은 공간의 방문 여부가 열쇠를 먹기 전과 먹은 후가 다르다는 것이다.

이를 위해 3차원 visited 배열을 선언해도 되지만 이렇게 하면 열쇠를 0개 먹었을 때 그래프를 모두 탐색하고 1개 먹었을 때 모두 탐색하고 거의 모든 경우를 탐색해보게 될 것이다. 따라서 현재 가진 열쇠 개수보다 더 적은 상태를 탐색하지 않게 추가적인 처리가 필요하다.

 

반면 아래 코드에서는 단순히 2차원 visited 배열을 선언하고 열쇠를 먹었을 때 방문 여부를 전체 초기화시켜줬다. 그리고 큐에 있는 요소를 모두 제거한 뒤 열쇠를 먹은 자리에서부터 탐색을 하게 만들었다. 또, 열쇠를 먹은 즉시 문을 모두 빈 공간으로 만들어주었다.

코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int h, w;
        bool hasKeys[28] = {false,};
        char keys[28] = {0,};
        scanf("%d %d", &h, &w);
        vector<vector<char>> v(h+2, vector<char>(w+2, '.'));
        vector<vector<bool>> visited(h+2, vector<bool>(w+2, false));
        for(int i=1; i<=h; i++)
        {
            for(int j=1; j<=w; j++)
            {
                char c;
                scanf(" %1c", &c);
                v[i][j] = c;
            }
        }
        scanf("%s", keys);
        for(int i=0; keys[i]!='\0'; i++)
        {
            hasKeys[keys[i]-'a'] = true;
            for(int j=1; j<=h; j++)
            {
                for(int k=1; k<=w; k++)
                {
                    if(v[j][k]-'A' == keys[i]-'a')
                        v[j][k] = '.';
                }
            }
        }
        
        int answer = 0;
        queue<pair<int, int>> q;
        q.push({0,0});
        visited[0][0] = true;
        while(!q.empty())
        {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            for(int i=0; i<4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(ny < 0 || ny >= h+2 || nx < 0 || nx >= w+2)
                    continue;
                if(v[ny][nx] == '*' || visited[ny][nx]) 
                    continue;
                // 열쇠
                if('a' <= v[ny][nx] && v[ny][nx] <= 'z' )
                {
                    // 해당 열쇠를 갖고 있지 않을 경우
                    if(!hasKeys[v[ny][nx]-'a'])
                    {
                        hasKeys[v[ny][nx]-'a'] = true;
                        // 문 열기
                        for(int j=1; j<=h; j++)
                        {
                            for(int k=1; k<=w; k++)
                            {
                                if((v[j][k]-'A') == (v[ny][nx]-'a'))
                                {
                                    v[j][k] = '.';
                                }
                            }
                        }
                        // 방문 기록 초기화
                        fill(visited.begin(), visited.end(), vector<bool>(w+2, false));
                        while(!q.empty()) q.pop();
                    }
                	visited[ny][nx] = true;
                	q.push({ny,nx});
                    v[ny][nx] = '.';
                }
                // 빈 공간
                else if(v[ny][nx] == '.')
                {
                    visited[ny][nx] = true;
                    q.push({ny,nx});
                }
                // 문서
                else if(v[ny][nx] == '$')
                {
                    visited[ny][nx] = true;
                    q.push({ny,nx});
                    answer++;
                    v[ny][nx] = '.';
                }
            }
        }
        printf("%d\n", answer);
    }
    return 0;
}

고찰

혹시 문제 해결에 어려움을 겪고 있다면 아래 글에서 테스트 케이스를 참고해보자.

https://www.acmicpc.net/board/view/69162

글 읽기 - TC 공유합니다.