[9328] 열쇠

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

주어진 정보로 상근이가 몇 개의 문서를 훔칠 수 있는지를 묻는 문제이다.

그래프 탐색문제이므로 BFS로 풀면 되지만 문제가 까다롭다.

바로 열쇠를 획득했을 때 이전에 탐색했던 문을 다시 찾아가 열고 또 계속해서 탐색을 진행할 수 있다는 점이었는데

처음에 문제를 풀 때는 너무 일차원적으로 생각해서

그냥 열쇠를 획득하면 빌딩 입구(테두리 중에서 '*'이 아닌 곳)들을 다시 처음부터 탐색을 진행했다.

즉 빌딩 입구들을 벡터에 다 넣어놓고 for문을 돌면서 각 입구마다 bfs를 진행하고

bfs진행중 열쇠를 만나면 그 열쇠지점을 '.'으로 바꾸고 for문을 다시 처음부터 수행하도록 했었는데

이렇게 하니까 시간이 무려 900ms가 넘었다. 예제가 조금만 더러워도 시간초과가 날거같아서

다시 풀었다.

열쇠를 찾아서 문제가 생기는 지점은 바로 문이다.

그러므로 bfs진행 중 만나는 문들 중 현재 나에게 열쇠가 있는 문이면 '.'로 바꿔주고

만약 현재 못여는 문이라면 벡터에 저장해둔다.

그 후 bfs탐색 중 열쇠를 찾게되면 벡터에 넣어놨던 좌표 중 현재 열쇠로 열 수 있는 문 좌표를 bfs의 시작 정점으로 큐에 넣어준다.

이렇게 하면 bfs 시작 정점으로 문 차례가 되었을 때 문 까지 가는 통로는 visit으로 처리되어 있으므로 문 너머를 탐색하게 된다.

다만 함정이 하나 있는데

문은 하나가 아니라 여러개일 수 있으므로

각 문에 해당하는 벡터를 다 따로 만들어서 관리해 줘야 한다.  간단하게 이차원 벡터를 만들어 주면 된다.

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
char arr[110][110];
bool visit[110][110];
int key[26];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int n, m;
 
int bfs(queue<pair<int, int> > qu) {
    vector< pair<int, int> > vt[26];
    int cnt = 0;
    while (int s = (int)qu.size()) {
        while (s--) {
            int cx = qu.front().first;
            int cy = qu.front().second;
            qu.pop();
 
            if (arr[cx][cy] == '$') {
                arr[cx][cy] = '.';
                cnt++;
            }
            else if (arr[cx][cy] >= 'a' && arr[cx][cy] <= 'z') {
                if (!vt[arr[cx][cy]-'a'].empty()) {
                    for (int i = 0; i < (int)vt[arr[cx][cy] - 'a'].size(); i++) {
                        int vx = vt[arr[cx][cy] - 'a'][i].first;
                        int vy = vt[arr[cx][cy] - 'a'][i].second;
                        qu.push({ vx, vy });
                    }
                    vt[arr[cx][cy] - 'a'].clear();
                }
                key[arr[cx][cy] - 'a'] = 1;
                arr[cx][cy] = '.';
            }
            else if (arr[cx][cy] >= 'A' && arr[cx][cy] <= 'Z') {
                if (key[arr[cx][cy] - 'A'])
                    arr[cx][cy] = '.';
                else {
                    vt[arr[cx][cy] - 'A'].push_back({ cx, cy });
                    continue;
                }
            }
 
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + cx;
                int ny = dy[i] + cy;
 
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny] ||
                    arr[nx][ny] == '*') continue;
                visit[nx][ny] = 1;
                qu.push({ nx, ny });
            }
 
        }
    }
    return cnt;
}
 
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        memset(arr, 0, sizeof(arr));
        memset(key, 0, sizeof(key));
        memset(visit, 0, sizeof(visit));
        scanf("%d %d", &n, &m);
        queue<pair<int, int> >qu;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf(" %1c", &arr[i][j]);
                if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {
                    if (arr[i][j] != '*') qu.push({ i, j });
                }
            }
        }
        string str;
        cin >> str;
        for (int i = 0; i < (int)str.size(); i++) {
            if (str[i] == '0') break;
            key[str[i] - 'a'] = 1;
        }
        int res = bfs(qu);
 
        printf("%d\n", res);
    }
}