[백준/C++] 9328번 열쇠

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

9328번: 열쇠

 

문제 분석

전형적인 그래프 탐색 문제이지만, 열쇠가 없어서 지나쳤던 문을 이후에 열쇠를 획득했을 때 재방문해서 탐색하는 것을 구현하기가 약간 까다로울 수 있습니다. 하지만 그것만 구현하면 나머지는 평범한 그래프 탐색 문제이기 때문에 그렇게 어렵지 않습니다. 차근차근 문제에 접근해봅시다.

 

문제 풀이

빌딩을 탐색하다가, 열쇠가 없어서 열고 지나가지 못하는 문이 문제입니다. 열지 못했던 문을 기억해뒀다가 이후 그 문을 열 수 있는 열쇠를 획득했을 때 재방문하면 됩니다. 문은 A~Z까지 있으므로 A~Z에 대응하는 리스트를 만들고, 열고 지나가지 못했던 문이 있는 좌표를 리스트에 기록해두면 됩니다. 예를 들어, (3, 4)와 (5, 3)에서 문 A를 마주쳤는데 열쇠 a가 없어서 지나가지 못했다면 리스트 A에 (3, 4)와 (5, 3)을 기록해둡니다. 이후 열쇠 a를 획득하면, 리스트 A에 기록해뒀던 대로 (3, 4)와 (5, 3)을 재방문하면 됩니다.

그런데 어떻게 재방문해야 할까요? BFS로 구현한다면 쉽게 해결할 수 있습니다. 방문해야 할 좌표들이 큐에 저장되므로 그냥 (3, 4)와 (5, 3)을 enqueue 해주기만 하면 됩니다. BFS로 어떻게 탐색해야 할지 정리해봅시다.

1. 큐에서 최상위 요소, 즉 방문할 좌표를 가져옵니다.
2. 방문할 좌표가 이미 방문했거나, 벽이거나, 탐색 범위를 벗어난다면 방문하지 않습니다.
3. 방문할 좌표가 빈 공간이면 방문 처리합니다.
4. 방문할 좌표에 문서가 있다면 방문처리 한 뒤, 획득한 문서 수에 1을 더해줍니다.
5. 방문할 좌표에 문이 있다면 그 문을 열 수 있는 열쇠를 가지고 있는지 확인합니다.
   1) 열쇠가 있다면 방문하고, 방문 처리합니다.
   2) 열쇠가 없다면 그 문의 리스트에 좌표를 저장해둡니다.
6. 방문할 좌표에 열쇠가 있다면 방문처리 한 뒤, 해당 열쇠를 획득했음을 기록하고, 그 열쇠로 열 수 있는 문들의 좌표를 enqueue합니다. 이후 그 문의 리스트를 비워줍니다. (이미 열고 지나간 문을 재방문할 필요가 없습니다.)
7. 방문한 좌표의 주변 네 개의 좌표를 enqueue합니다.

 

코드

#include<iostream>
#include<queue>
#include<string>
#include<memory.h>

using namespace std;

int T, h, w, idx, ans, x, y, dx[4]={-1, 1, 0, 0}, dy[4]={0, 0, -1, 1};
char map[100][100];
bool my_keys[26], visited[100][100];
string str;
queue<pair<int, int>> que;
vector<pair<int, int>> doors[26];

void go(int i, int j)
{
    if(i<0 || i>=h || j<0 || j>=w) return;
    if(map[i][j]=='*' || visited[i][j]) return;

    if(map[i][j]=='.')
    {
        visited[i][j]=true;
        que.push({i, j});
    }
    else if(map[i][j]=='$')
    {
        ans+=1;
        visited[i][j]=true;
        que.push({i, j});
    }
    else if(map[i][j]-'a'<0) //대문자
    {
        idx=map[i][j]-'A';

        if(my_keys[idx]) //열쇠가 있을 때
        {
            visited[i][j]=true;
            que.push({i, j});
        }
        else //열쇠가 없을 때
        {
            doors[idx].push_back({i, j});
        }
    }
    else //소문자
    {
        idx=map[i][j]-'a';

        my_keys[idx]=true;
        visited[i][j]=true;
        que.push({i, j});
        for(pair<int, int> next:doors[idx])
        {
            visited[next.first][next.second]=true;
            que.push(next);
        }
        doors[idx].clear();
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>T;

    while(T--)
    {
        cin>>h>>w;
        ans=0;
        memset(my_keys, false, sizeof(bool)*26);
        memset(visited, false, sizeof(bool)*100*100);
        for(int i=0; i<26; i++) doors[i].clear();

        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                cin>>map[i][j];
            }
        }

        cin>>str;

        if(str[0]!='0')
        {
            for(char c:str) my_keys[c-'a']=true;
        }
        
        for(int i=0; i<h; i++)
        {
            go(i, 0);
            go(i, w-1);
        }
        
        for(int j=0; j<w; j++)
        {
            go(0, j);
            go(h-1, j);
        }
    
        while(!que.empty())
        {
            x=que.front().first;
            y=que.front().second;
            que.pop();

            for(int k=0; k<4; k++)
            {
                go(x+dx[k], y+dy[k]);
            }
        }

        cout<<ans<<'\n';
    }
    return 0;
}

 

빌딩 바깥쪽을 모두 방문해보는 것으로 시작합니다. 테스트 케이스마다 열쇠 획득 여부와 방문 여부 등을 잘 초기화해줍시다.