[ 백준 9328 ] 열쇠 (C++)

백준의 열쇠(9328) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 문제를 다시 한번 되새겨보면, 소문자 알파벳으로 대문자의 문들을 열어가면서 훔칠 수 있는 문서의 최댓값을 구해야 하는

   문제이다.

   문제를 풀기 전, 본인이 생각하는 이 문제에서 가장 핵심적인 부분들에 대해서 말해보겠다.

   첫번째는 바로 "내가 지금 당장은 문을 열지 못해서 훔치지 못하는 문서가 있을 수 있지만, 한참 후에 열쇠를 줍는다

   면 그 문서는 훔칠 수 있다" 는 것이다. 문제를 읽어보면 너무나도 당연하게 알 수 있는 내용이지만, 문제를 까다롭게 만드

   는 중요한 단서라고 생각한다. 여기서 우리는 한 단계 더 나아가서 생각을 해봐야 한다.

   < 현재가진 키 : z >

   이러한 맵이 있다고 가정해보자. 우리는 빨강색으로 표시한 문서를 훔칠 수 있을까? (3, 3)에 있는 b라는 열쇠를

   주워온다면 B 문을 열 수 있을 것이고 결국 훔칠 수 있을 것이다. 하지만 우리가 늘 하던 BFS문제라고 생각한다면,

   아마 위의 맵에서 ' . ' 으로 표시된 부분은 'b'열쇠를 찾으러 가는 길에 모두 이미 탐색을 한 지점이라고 체크가 되어 버릴

   것이다. 즉, 우리는 b열쇠를 찾는 순간 B문이 있는 곳으로 갈 수 있는 방법을 생각해 봐야 한다.

   왜냐하면, 위에서 말했다시피, 이미 탐색한 지점을 다시 되돌아 갈 수는 없기 때문이다.

   해결책으로 탐색한 정점을 체크를 안해버리면 된다고 생각한다면, 크게 잘못된 생각이다. 직접 해보면 알겠지만

   코드가 끝나지 않을 것이다 !

   두번째는 바로 시작점이 정해져 있지 않다는 것이다. 시작점을 정할 수 있는 수없이 많은 방법이 있겠지만, 본인은 본인이

   풀이한 방법에 대해서 밑에서 설명하겠다.

2) 1)에서 말한 2가지를 해결해놓고 본격적으로 문제를 풀어보자. 먼저 2번내용(시작점이 정해져있지않다는 것) 부터 설명을

   해보겠다. 본인은 맵을 입력받을 때 (0, 0)에서부터가 아닌 (1, 1) ~ (H, W)까지 입력을 받았다.

   하지만 탐색의 시작은 (0, 0)에서 부터 하였다. 음... 맵을 감싸고 있는 하나의 테두리가 더 있다고 생각하면 쉽다.

   즉, 3x3의 맵을 입력받는다면...

  

   이런식으로 구현하였다. 파랑색은 실제 문제에서 주어지는 맵을 저장하는 공간이고, 빨강색은 본인인 입구를 찾기 위해

   탐색한 정점들이다. 즉, 맵의 모든 테두리를 돌면서 들어갈 수 있는 곳이라면, 그 길을 통해서 입구로 들어가는 방식으로

   구현을 하였다. 밑에 코드를 본다면 이해하기 어려운 부분은 없을 것이다.

   1)에서 말한 1번 내용의 해결책에 대해서 알아보자. 1번을 간략하게 다시 설명하자면 "열쇠를 주우면, 이미 탐색을 했던

   정점들을 모두 거슬러, 그 열쇠로 열 수 있는 문들로 순간이동을 해야 한다" 이다.

   이 부분을 해결하기 위해서, 본인은 크기가 26인 Queueu를 하나 사용하였다. 크기가 26인 이유는 알파벳이 26개이기 때문

   이고, 이 큐의 역할은 열 수 없는 문을 만났을 때, 그 문의 위치를 저장한다.

   Door[26] 으로 선언해놓자 ! 주의해야 할 점은, Queue가 2개라는 점에 주의하자.

   밑에 설명에서도 헷갈리지 않게, 우리는 현재 BFS를 진행하는 Queue 하나와, 열 수 없는 문을 만났을 때, 문의 좌표를

   저장해 놓는 크기가 26인 Queue 2개를 사용한다.

3) 본격적으로 문제를 풀어보자. 먼저 본인이 사용한 배열들에 대해 설명하자면

   MAP[][], Visit[][], Key[26] 을 사용하였다. MAP은 우리가 입력받는 맵의 상태를 저장하는 2차원 배열,

   Visit은 해당 정점을 탐색했는지 안했는지를 체크해주는 배열, Key[26]은 열쇠를 가지고 있는지 아닌지 판단하는 배열이다

   문제에서 초기에 가지고 있는 키를 가르쳐준다. 예를 들어서 키 a를 가지고 있다면 Key['a' - 'a'] = true 가 되는 것이다.

   초기에 가지고 있는 키를 먼저 말한대로 true라고 표시해주고 시작해보자.

   이제, 본인의 풀이대로 시작점을 찾기 위해서 (0, 0)부터 Queue에 집어 놓고 BFS를 실행시킨다.

   BFS안에서의 조건들에 대해서 알아보자.

   [ 조건 1 ] - 탐색할 범위

   먼저 본인은 입력받은 맵의 범위보다 한칸 더 작은 칸에서 시작한다. 즉, 맵의 범위가 (1, 1) ~ (H, W)이지만 본인은

   (0, 0) ~ (H+1, W+1) 의 범위까지 탐색을 진행한다.

   [ 조건 2 ] - 문을 만났을 경우

   문을 만났을 경우, 할 수 있는 것이 2개로 나뉜다. 해당 문에 대한 열쇠를 가지고 있어서, 그 열쇠를 통해서 그 문을 열수

   있는지, 아니면 그 반대인지...

   문을 열 수 있다면, 그대로 Queue에 넣어주고 계속 진행을 하면 된다. 문제는 문을 열 수 없을 때이다.

   이제 본인이 위에 밑줄 그어놓은 문장으로 다시 가보자. 열 수 없는 문을 만나면 그 문의 위치를 저장한다 !

   열 수 없는 문이라면, Queue에 담을 수 없을 것이고, 그 방향으로는 탐색이 더이상 불가능하다.

   하지만, 언젠가 열 수도 있는 문일 수도 있기 때문에 Queue에 저장해준다.

   ( 여기서 말하는 Queue가 현재 BFS를 진행하는 Queue가 아닌, 따로 하나 더 만들어놓은 Door[26] Queue를 의미한다. )

   예를 들어 (a, b) 좌표에 있는 A라는 문을 현재 열 수 없다면, Door[A].push(a,b) 이런식으로 문의 좌표를

   저장해준다. 그렇다면, A ~ Z 까지, 열 수 없는 문들이 해당 Index에 쭉 들어가 있을 것이다.

   [ 조건 3 ] - 열쇠를 만났을 경우

   열쇠를 만났을 경우, 해당 열쇠를 이미 가지고 있다면 Queue에 넣어주고 계속 진행만 하면 된다.

   하지만, 기존에 없었던 새로운 열쇠를 주웠다면, 주운 열쇠를 Key[] 배열로 주웠다는 표시를 먼저 해주자.

   그리고.... 이 열쇠로 열 수 있는 문이 존재할 지도 모른다. [ 조건2 ] 에서 열 수 없는 문이라서 Queue에 저장해놓은

   문을 이제는 열 수 있다. 여기서, 주운 열쇠로 열 수 있는 문의 좌표를 우리가 진행하는 BFS Queue에 옮겨 주자 !

   물론, 해당 문의 Queue가 모두 없을 때 까지 다 빼주면서 ! 이후 BFS를 계속 진행하면 된다 !

   조건 3에 대해서 조금 더 알아보자... (말로 하려니까 진짜 어렵다...)

   이런 맵이 있다고 생각해보자. 초기에 가지고 있는 키는 없다.

   현재라고 표시된 정점을 (1, 1)로, 가장 오른쪽 아래에 a키가 있는 정점을 (5, 5)로 생각하고 설명하겠다.

   이 경우, 정점 하나씩 탐색을 하다보면 열 수 없는 문 A, A, B, B, C, C를 만나게 된다.

   그렇다면, 열 수 없는 문을 Queue에 저장해주자.

   Door[A].push((3,1), (3,2))

   Door[B].push((3,4), (3,5))

   Door[C].push((1,4), (2,4))

   이런식으로 Queue에 저장이 되 있을 것이다. 이후, a라는 열쇠를 줍게 될 것이고 a라는 열쇠를 주우면

   A문을 저장해놓은 Door[A]로 접근을 한다. 접근을 해서, 저장되어 있는 (3,1), (3,2) 를 BFS가 진행되고 있는

   Queue로 옮기고 진행을 계속 하면 된다.

   코드를 보게 된다면 이해가 될 것이다...

 

4) 문제가 설명이 길어서 그렇지 막상 코드를 보면 그렇게 어렵지 않을 것이다.

   또한, 이 문제를 통해서 소문자와 대문자 알파벳들을 인덱스 번호로 바꾸는 연습을 많이 했으면 좋겠고

   그런 사람이라면 보다 쉽게 이해할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 111
using namespace std;
 
int H, W, Answer;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Key[26];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
string First_Key;
 
void Initialize()
{
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
    memset(Key, false, sizeof(Key));
    First_Key.clear();
    Answer = 0;
}
 
void Input()
{
    cin >> H >> W;
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            cin >> MAP[i][j];
        }
    }
 
    cin >> First_Key;
    for (int i = 0; i < First_Key.length(); i++)
    {
        if (First_Key[i] == '0') continue;
        Key[First_Key[i] - 'a'] = true;
    }
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q;
    queue<pair<int, int>> Door[26];
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx <= H + 1 && ny <= W + 1)
            {
                if (MAP[nx][ny] == '*' || Visit[nx][ny] == true) continue;
                Visit[nx][ny] = true;
 
                if ('A' <= MAP[nx][ny] && MAP[nx][ny] <= 'Z')
                {
                    if (Key[MAP[nx][ny] - 'A'] == true)
                    {
                        Q.push(make_pair(nx, ny));
                    }
                    else
                    {
                        Door[MAP[nx][ny] - 'A'].push(make_pair(nx, ny));
                    }
                }
                else if ('a' <= MAP[nx][ny] && MAP[nx][ny] <= 'z')
                {
                    Q.push(make_pair(nx, ny));
                    if (Key[MAP[nx][ny] - 'a'] == false)
                    {
                        Key[MAP[nx][ny] - 'a'] = true;
 
                        while (Door[MAP[nx][ny] - 'a'].empty() == 0)
                        {
                            Q.push(Door[MAP[nx][ny] - 'a'].front());
                            Door[MAP[nx][ny] - 'a'].pop();
                        }
                    }
                }
                else
                {
                    Q.push(make_pair(nx, ny));
                    if (MAP[nx][ny] == '$') Answer++;
                }
            }    
        }
    }
}
 
void Solution()
{
    BFS(0, 0);
}
 
void Solve()
{
    int Tc;
    cin >> Tc;
 
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}