[BOJ-9328]열쇠

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

[접근방법]

시간초과 받을까봐 어떻게 줄여야 할지 계속 생각했던 문제 

코드 작성 전부터 BFS를 계속 돌리면 시간초과 받을 것 같은데 라고 생각해서 코드 작성하기 망설였던 문제....

열쇠를 획득하면 해당 열쇠에 열리는 문은 모두 열 수 있다. 

다시 처음 건물 밖 위치부터 BFS 탐색을 해나아간다. 

문서를 획득하면 ans +1 을 하여, 값을 출력하면 된다.

[C++11 source Code BFS]

#include<cstdio>
#include<queue>
#include<vector>
#include<memory.h>
using namespace std;
 
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };
const int M = 111;
 
struct pos {
    int r, c;
    pos() {}
    pos(int ir, int ic) : r(ir), c(ic) {}
};
typedef vector<pos> vpos;
char imap[M][M];
vpos key_set[M];
vpos door_set[M];
bool vis[M][M];
 
int RO, CO;
 
 
void init() {
    for (int r = 0; r < M; r++) memset(imap[r], 0x00, sizeof(imap[r]));
    for (int r = 0; r < 33; r++) key_set[r].clear(), door_set[r].clear();
    memset(vis, 0x00, sizeof(vis));
}
 
int main() {
    int t;
    char tmp[M];
    for (scanf("%d", &t); t > 0 ; t-- ) {
        scanf("%d%d", &RO, &CO);
        init();
        for (int r = 1; r <= RO; r++) {
            memset(tmp, 0x00, sizeof(tmp));
            scanf("%s", tmp);
            for (int c = 1; c <= CO; c++) {                
                imap[r][c] = tmp[c - 1];
                if ('a' <= imap[r][c] && imap[r][c] <= 'z') {
                    key_set[imap[r][c] - 'a'].push_back(pos(r, c));
                }
                else if ('A' <= imap[r][c] && imap[r][c] <= 'Z') {
                    key_set[imap[r][c] - 'A'].push_back(pos(r, c));
                }
            }
        } // input;
 
        memset(tmp, 0x00, sizeof(tmp));
        scanf("%s", tmp);
        int hav_key = 0;
        for (int i = 0; tmp[i] != NULL; i++) {
            if (tmp[i] == '0') break;
            int k = tmp[i] - 'a';
            hav_key = hav_key | (1 << k);        
            for (auto p : door_set[k]) imap[p.r][p.c] = '.';
            for (auto p : key_set[k]) imap[p.r][p.c] = '.';
        }
 
        queue<pos> Q;
        pos start = pos(0, 0);
        Q.push(start);
        int ans = 0;
        vis[0][0] = true;
        while (!Q.empty()) {
            pos here = Q.front(); Q.pop();
            int hr = here.r;
            int hc = here.c;
 
            for (int i = 0; i < 4; i++) {
                int tr = hr + dr[i];
                int tc = hc + dc[i];
 
                if (tr < 0 || RO+1 < tr || tc < 0 || CO+1 < tc) continue;
                if (imap[tr][tc] == '*') continue;
                if (vis[tr][tc]) continue;
                if ('$' == imap[tr][tc]) {
                    ans++;
                    imap[tr][tc] = '.';
                    Q.push(pos(tr, tc));
                    vis[tr][tc] = true;
                }
                else if ('a' <= imap[tr][tc] && imap[tr][tc] <= 'z') {
                    int k = imap[tr][tc] - 'a';
                    for (auto p : door_set[k]) imap[p.r][p.c] = '.';
                    for (auto p : key_set[k]) imap[p.r][p.c] = '.';
                    Q = queue<pos>();
                    Q.push(pos(0, 0)); // 새롭게 돈다.                    
                    memset(vis, 0x00, sizeof(vis));
                    vis[0][0] = true;
                }
                else if (imap[tr][tc] == '.' || imap[tr][tc] == 0) {
                    Q.push(pos(tr, tc));
                    vis[tr][tc] = true;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}