BOJ 9328 열쇠 [C++]

또한 빡센 구현, 시뮬레이션 문제이다.

요즘 문제가 어려워질수록 구현 자체의 난이도도 높아지는 듯 하다.

이 문제는 특히 문자를 사용해서 손도 대기 꺼리게 만드는 것 같다.

 

먼저 시간복잡도는 고려하지 않아도 된다. 완전탐색도 아니고 문제 사이즈도 작은데다, bfs자체가 그리 오래걸리지 않는다. 아래 코드로 8ms 소비하여 AC를 받았다.

 

문제는 먼저 건물 지도를 입력받는다. 입력받을 때 문이 있다면,  그 문의 좌표를 문의 종류에 맞는 doors라는 벡터에 삽입해준다.

상근이에게 처음 주어진 열쇠는 종류에 맞는 문이 존재한다면 그 문을 모두 연다.

당장 문에 도달하지 못한다고 해도 추후에 그 문에 도달하면 문을 열 것이므로 그냥 다 연다.

여기서 효율성을 좀더 높이려면 열린 문은 벡터에서 빼버려도 된다. 큐를 사용할수도 있고. 하지만 귀찮아서 안했다.

 

그리고

1. 테두리를 체크해준다. 이때 테두리에 빈공간 뿐만 아니라 문서, 열쇠가 있는 경우도 체크해준다.

 벽은 체크하지 않고 문은 입력과정에서 이미 체크되어 door벡터에 들어있다.

 

 

2. 큐가 빌 때까지 bfs를 해준다.(while(!q.empty()))

 

2-1. 현재 위치에 열쇠가 있다면 입력과정과 같이 해당 열쇠에 맞는 문을 모두 연다. 이때 열쇠를 주운 자리는 '.' 즉 빈공간으로 바꾸어준다. 

 

2-2. 상하좌우 좌표로 이동한다.

첫번째로 이동한 좌표가 범위 안에 존재하는지 확인(아니라면 continue)

두번째로 이미 방문한것은 아닌지 확인(이미 방문했다면 continue)

세번째로 이동한 좌표가 벽( * )이거나 문(대문자 알파벳)인 경우는 큐에 넣지 않는다.

문서, 열쇠는 큐에서 pop될때 처리할 것이다.

 

2-3. 열쇠로 문을 열었다면 재시작하게한다. 이때 현재 방문가능한 모든 열쇠를 처리한 후 재시작하기 위해서는

2-1에 위치한 restart = true를 실행한 후에 즉시 break;를 하면 안된다.

 

3. restart == true라면 가장 바깥 while 문을 재시작한다. 즉 1~3 전체를 반복한다.

restart == false라면 상근이가 얻을 수 있는 문서 개수를 출력한 후 테스트케이스를 끝낸다.

#include <bits/stdc++.h>

using namespace std;

int di[] = { 1,-1,0,0 };
int dj[] = { 0,0,1,-1 };

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

    int t;
    cin >> t;

    for (int tt = 0; tt < t; tt++) {
        int h, w, ans = 0;
        cin >> h >> w;

        vector<vector<char>> mama(h, vector<char>(w));
        vector<pair<int, int>> doors[130];

        for (int i = 0; i < h; i++) {
            string s;
            cin >> s;

            for (int j = 0; j < w; j++) {
                if (s[j] >= 'A' && s[j] <= 'Z') {
                    doors[s[j] + 32].push_back({ i,j });
                }

                mama[i][j] = s[j];
            }
        }

        string keys;
        cin >> keys;
        if (keys[0] != '0')
            for (int j = 0; j < keys.length(); j++) {
                for (int k = 0; k < doors[keys[j]].size(); k++) {
                    mama[doors[keys[j]][k].first][doors[keys[j]][k].second] = '.';
                }
            }

        bool restart = false;

        while (true) {

            /*for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    cout << mama[i][j];
                }
                cout << endl;
            }
            cout << endl;*/

            queue<pair<int, int>> q;
            bool visited[100][100] = { false };

            for (int i = 0; i < w; i++) {
                if (mama[0][i] == '.' || (mama[0][i] >= 'a' && mama[0][i] <= 'z') || mama[0][i]=='$') {
                    q.push({ 0,i }); visited[0][i] = true;
                }
                if (mama[h - 1][i] == '.' || (mama[h - 1][i] >= 'a' && mama[h - 1][i] <= 'z') || mama[h-1][i] == '$') {
                    q.push({ h - 1,i }); visited[h - 1][i] = true;
                }
            }

            for (int i = 0; i < h; i++) {
                if (mama[i][0] == '.' || (mama[i][0] >= 'a' && mama[i][0] <= 'z') || mama[i][0] == '$') {
                    q.push({ i,0 }); visited[i][0] = true;
                }
                if (mama[i][w - 1] == '.' || (mama[i][w - 1] >= 'a' && mama[i][w - 1] <= 'z') || mama[i][w-1] == '$') {
                    q.push({ i,w - 1 }); visited[i][w - 1] = true;
                }
            }

            while (!q.empty()) {
                int nowi = q.front().first;
                int nowj = q.front().second;
                q.pop();


                if (mama[nowi][nowj] >= 'a' && mama[nowi][nowj] <= 'z') {
                    int j = mama[nowi][nowj];
                    for (int k = 0; k < doors[j].size(); k++) {
                        mama[doors[j][k].first][doors[j][k].second] = '.';
                    }
                    mama[nowi][nowj] = '.';

                    restart = true;
                }

                if (mama[nowi][nowj] == '$') { mama[nowi][nowj] = '.'; ans++; }

                for (int i = 0; i < 4; i++) {
                    int ni = nowi + di[i];
                    int nj = nowj + dj[i];

                    if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
                    if (visited[ni][nj]) continue;
                    if (mama[ni][nj] == '*' || (mama[ni][nj] >= 'A' && mama[ni][nj] <= 'Z')) continue;

                    visited[ni][nj] = true;
                    q.push({ ni,nj });

                }

            }
            if (restart) {
                restart = false;
                continue;
            }
            cout << ans << "\n";
            break;
        }

    }

}