9328번

9328번 - 열쇠

푸는데 3~4시간 정도 걸린 것 같다... 마치 BFS와 시뮬레이션 문제를 섞어놓은 듯했다.. 나한테는

일단 기본적인 로직은 , BFS를 계속 돌리면서 찾을 수 있는 열쇠랑, 문서를 다 찾는 것이다.

문제에서 기본맵의 바깥에서 들어오기 때문에, 가장 바깥쪽 테두리만을 검사하고 BFS를 수행하도록 2중 for문을 이용했다.

그럼 문제는 BFS를 몇번 돌리냐 인데, 나는 새로운 열쇠를 발견하면 BFS를 돌리도록 하였고, 찾지 못하면 더 이상 BFS를 돌리지 않았다.

열쇠를 찾느냐 마느냐는 updated 변수를 이용해서 나타냈다. 열쇠는 중복되지 않도록 map 을 이용해서 구현하였다.

그리고 열쇠를 찾거나, 열쇠를 통해서 문을 열수 있거나, 문서를 찾으면, 그 지역을 그냥 통과할 수 있는 . 로 바꾸어 주었다.

틀린 테스트 케이스를 보면서, 코드를 고쳐나갔는데, 내가 빼먹었던 점은.

처음에 나는 맵의 바깥쪽 테두리에 . 일 때만 진입가능하도록 했는데, 사실 $ 나 열쇠가 있는 문은 통과할 수 있게 고쳐줘야 했다.

그걸 main 의 while 문에서 다시 재설정해줘서 문제를 맞을 수 있었다. 또 그대신 탐색할때 자기자신도 탐색하도록 고쳐줬다.

실수하기 정말 좋은 문제인 것 같다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
#include<map>
using namespace std;
 
int dx[5] = { 0,0,1,-1,0 };
int dy[5] = { 1,- 1, 0 ,0,0 };
int ans;
int h, w;
map<char, bool> key;
bool check[101][101];
bool cango[101][101];
void BFS(int a,int b,bool &updated, vector<vector<char>> &mapp)
{
    queue<pair<int, int>> q;
    q.push({ a, b });
    
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 5; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < h && ny < w  && mapp[nx][ny] != '*' && !check[nx][ny])
            {
                if (mapp[nx][ny] >= 'a' && mapp[nx][ny] <= 'z')
                {
                    key[mapp[nx][ny]] = true;
                    check[nx][ny] = true;
                    updated = true;
                    mapp[nx][ny] = '.';
                    q.push({ nx,ny });
                }
                else if (mapp[nx][ny] >= 'A' && mapp[nx][ny] <= 'Z')
                {
                    if (key.count(mapp[nx][ny] - 'A' + 'a') != 0)
                    {
                        mapp[nx][ny] = '.';
                        q.push({ nx,ny });
                        break;
                    }
                }
                else if(mapp[nx][ny]=='.')
                {
                    check[nx][ny] = true;
                    q.push({ nx,ny });
                }
                else if(mapp[nx][ny]=='$')
                {
                    ans++;
                    mapp[nx][ny] = '.';
                    check[nx][ny] = true;
                    q.push({ nx,ny });
                }
            }
        }
    }
    
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        ans = 0;
        key.clear();
        scanf("%d%d", &h, &w);
        vector<vector<char>> mapp(h, vector<char>(w));
        
 
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> mapp[i][j];
                //scanf("%c", &map[i][j]);
            }
        }
 
        string tmp;
        cin >> tmp;
        for (int i = 0; i < tmp.size(); i++)
        {
            key[tmp[i]] = true;
        }
        
 
        bool updated = true;
 
        while (updated)
        {
            updated = false;
            memset(check, false, sizeof(check));
 
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    if (i == 0 || j == 0 || i == h - 1 || j == w - 1)
                    {
                        if ((mapp[i][j] != '*' && !check[i][j]))
                        {
                            if(mapp[i][j]>='A' && mapp[i][j]<='Z')
                            {
                                if (key.count(mapp[i][j] - 'A' + 'a') != 0)
                                {
                                    BFS(i, j, updated, mapp);
                                }
                            }
                            else
                            {
                                BFS(i, j, updated, mapp);
                            }
                        }
                    }
                }
            }
        }
 
        printf("%d\n", ans);
        
 
    }
    return 0;
}