9328 열쇠

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

9328번: 열쇠

 

가지고 있는 열쇠와 빌딩 바닥에 놓인 열쇠를 가지고 잠긴 문을 열어 가져울 수 있는 문서의 최대 개수를 구하는 문제.

 

처음에 헷갈렸던 점은 우리가 찾아야할 것이 문서의 최대 개수라는 것이다. 문서를 가져오는데 걸리는 시간이 아니라.

문서를 모두 가져오는데 걸리는 시간이라고 문제에 적혀있지도 않은데 자연스럽게 그렇게 생각했다. 이런 비슷한 문제를 풀어봤다는 생각에 문제를 대충읽은 것이다.

 

그러다 다시 제대로 이해한 후 코드를 고치려고 했다.

여기서 두번째 실수가 나온 것이다. 이미 잘못이해했고 엉망이 된 코드를 다시 다 지우고 작성해야하는데 귀찮은 나머지 거기서 꾸역꾸역 고쳐쓴 것이다. 실수가 안나올래야 안나올 수가 없다.

 

문서를 가지고 나오는 데 걸리는 시간이 상관 없다보니, 빌딩을 돌면서 키를 가지고 있지 않은 잠긴 문을 만났을 때, 해당 위치를 저장하고 해당 문에 맞는 키를 찾으면 문으로 순간이동해도 상관없다.

 

상근이는 처음에 빌딩의 밖에 있다고 했으니, 입력값을 받고 빌딩 둘레를 빈공간으로 추가해줬다.

예시 입력1

빌딩 둘레에 빈공간을 추가해 준 모습.

Queue 26개로 모든 열쇠(알파벳)에 해당하는 문의 좌표를 저장하고, BFS 진행했다.

그리고 키는 항상 최대로 가지고 있으면 된다. 이를 boolean 배열 26개로 하면 되지만 코드를 재사용하다보니 비트마스킹으로 그냥 진행했다.

그리고 check 배열은 3가지 상태를 저장해야하므로 int로 저장했다.

0 -> 방문하지 않은 곳

1 -> 방문한 곳

-1 -> 방문했지만 아직 잠겨있는 문

 

그래서 키를 가지고 있지 않을 때 잠겨있는 문을 만나면 해당 Queue에 문의 좌표를 넣고 check는 -1로 저장했다.

키를 가지고 있다면 해당 문을 그냥 '.'으로 바꾸어 저장하고 진행했다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
 
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int32_t tc;
    cin >> tc;
    while(tc--)
    {
        int h, w;
        cin >> h >> w;
        vector<string> bd(h+2, ".");
        string tmp;
        for(int i=1;i<=h;i++)
        {
            cin >> tmp;
            bd[i] += tmp;
            bd[i].push_back('.');
        }
        tmp = "";
        for(int i=0;i<w+2;i++)
            tmp.push_back('.');
        bd[0] = bd[h+1] = tmp;
 
        h += 2;
        w += 2;
    
        int key = 0;
        string keys;
        cin >> keys;
        for(auto &KEY : keys)
        {
            if(KEY == '0') break;
            key |= (1<<(KEY-'a'));
        }
        int paper = 0;
        vector<vector<int>> check(h, vector<int>(w, 0));
        check[0][0] = 1;
        vector<queue<pair<int, int>>> locked(26, queue<pair<int, int>>());
        queue<pair<int, int>> q;
        q.push({0, 0});
        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], nx = x+dx[i];
                if(ny < 0 || nx < 0 || ny >= h || nx >= w || bd[ny][nx] == '*') continue;
                if(check[ny][nx] == 1) continue;
                if(bd[ny][nx] >= 'A' && bd[ny][nx] <= 'Z')
                {
                    if((key & (1 << (bd[ny][nx]-'A'))) == 0)
                    {
                        if(check[ny][nx] == -1) continue;
                        locked[bd[ny][nx]-'A'].push({ny, nx});
                        check[ny][nx] == -1;
                        continue;
                    }
                    else
                    {
                        bd[ny][nx] = '.';
                    }
                }
                if(bd[ny][nx] >= 'a' && bd[ny][nx] <= 'z')
                {
                    key |= (1 << (bd[ny][nx]-'a'));
                    while(!locked[bd[ny][nx]-'a'].empty())
                    {
                        q.push({locked[bd[ny][nx]-'a'].front()});
                        locked[bd[ny][nx]-'a'].pop();
                    }
                    bd[ny][nx] = '.';
                }
                if(bd[ny][nx] == '$')
                {
                    paper++;
                    bd[ny][nx] = '.';
                }
                q.push({ny, nx});
                check[ny][nx] = 1;
            }
        }
        cout << paper << endl;
    }
 
    return 0;
}