[BaekJoon] 9328 열쇠 :: monton

문제

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

풀이

bfs + 시뮬 문제

1. 경계면에 있는 '.'이나 '$', 소문자가 있다면 출발지로 모두 큐에 넣는다.

2. 상하좌우로 돌린다

3. visit 체크를 하면서 '*'은 피해준다

여기서 관건은 열쇠가 없어 지나갔던 문의 열쇠를 다시 획득하게 될 경우이다

나의 케이스 같은 경우는 열쇠를 얻을 때 이전에 열쇠가 없어 지나 갔던 문들 중에 맞는 열쇠의 문을 다시 큐에 넣어 주었다.

doorlist[H][W]를 만들어서 열쇠가 없지만 지나간 문들을 -1로 표시해 두었다

이후, 새로

운 열쇠를 얻게 될때마다 이전에 지나갔던 문과 비교해서 맞으면 다시 큐에 넣는 방식으로 하였다.

이번 문제에서 틀렸던 부분은 상하좌우로 움직일때 큐에 넣으면서 visit을 체크해 주었는데

그외 방법으로 큐에 새로운 좌표를 넣을 경우(ex. doorlist에서 -1로 표시해두었던 좌표를 큐에 넣을때) visit을 체크하는것을 빼먹어서 였다

완전 처참하다 ㅠㅜ

코드

#include <iostream>
#include <queue>
using namespace std;
 
int H, W, ans;
char arr[101][101];
int visit[101][101];
int doorlist[101][101];
int keys[27];
int dir[4][2] = { { -1,0 },{ 0,1 },{ 1,0 },{ 0,-1 } };
 
queue <int> qx, qy;
 
 
void checkdoor(int num) {
    for (int i = 0; i<H; i++) {
        for (int j = 0; j<W; j++) {
            if (doorlist[i][j] == -1 && arr[i][j] - 'A' == num) {
                qx.push(i), qy.push(j);
                doorlist[i][j] = 0;
                visit[i][j] = 1;
            }
        }
    }
}
 
 
void init() {
    for (int i = 0; i<H; i++) {
        for (int j = 0; j<W; j++) {
            visit[i][j] = doorlist[i][j] = 0;
        }
    }
    for (int i = 0; i<27; i++) keys[i] = 0;
    ans = 0;
    queue <int> empty;
    qx = qy = empty;
}
 
 
int main() {
    int T;
    cin >> T;
 
    for (int t = 0; t<T; t++) {
        cin >> H >> W;
        init();
        for (int i = 0; i<H; i++) {
            for (int j = 0; j<W; j++) {
                cin >> arr[i][j];
                if (i == 0 || i == H - 1 || j == 0 || j == W - 1) {
                    if (arr[i][j] == '.' || arr[i][j] == '$' || (arr[i][j] >= 'a'&&arr[i][j] <= 'z')) {
                        qx.push(i), qy.push(j);
                        visit[i][j] = 1;
                    }
                    if (arr[i][j] >= 'A'&&arr[i][j] <= 'Z') doorlist[i][j] = -1;
                }
            }
        }
 
        getchar();
        while (1)
        {
            char c = getchar();
            if (c == '0' || c == '\n') break;
            else keys[c - 'a'] = 1;
        }
 
        for (int i = 0; i<27; i++) {
            if (keys[i]) checkdoor(i);
        }
 
        //for(int i=0;i<26;i++) printf("%d ",key[i]);
 
        while (!qx.empty()) {
            int x = qx.front();
            int y = qy.front();
            qx.pop(), qy.pop();
 
            if (arr[x][y] == '$') ans++;
            if (arr[x][y] >= 'a'&&arr[x][y] <= 'z') {
                keys[arr[x][y] - 'a'] = 1;
                for (int i = 0; i<27; i++) {
                    if (keys[i]) checkdoor(i);
                }
            }
 
            if (arr[x][y] >= 'A'&&arr[x][y] <= 'Z') {
                if (keys[arr[x][y] - 'A'] != 1) {
                    doorlist[x][y] = -1;
                    continue;
                }
            }
 
            for (int i = 0; i<4; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
 
                if (nx<0 || nx >= H || ny<0 || ny >= W) continue;
                if (visit[nx][ny]) continue;
                if (arr[nx][ny] == '*') continue;
 
                qx.push(nx), qy.push(ny);
                visit[nx][ny] = 1;
            }
        }
        cout << ans << endl;
    }
}