[백준/C++] 9328번 열쇠

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

9328번: 열쇠

이 문제는 bfs에 구현을 섞은 문제이다. 총 3가지의 주요 로직으로 이루어져 있다.

​

1. 가장자리

입력부터 차근차근히 보자면, 입력을 받을 때 0행, 마지막 행, 첫 열, 마지막 열은 가장자리​로써 상근이가 자유로이 접근할 수 있기 때문에 모두 큐에 넣어주자.

그러나! 가장자리에는 벽이 올 수도 있고, 문 또는 키, 그리고 빈칸 모두가 올 수 있다. 그러므로 입력을 받을 때 이들을 걸러주자.

case1. 빈칸이 오는 경우

-> 큐에 넣고 방문 여부를 수정

case2. 벽이 오는 경우

-> 패스

case3. 문이 오는 경우

-> 키가 없는 경우 2차원 큐에 넣는데, 삽입 시 문에 해당하는 인덱스에 넣어준다 (= 문을 알파벳이기 때문에 -65 또는 -97을 통해서 인덱스화 시킬 수 있다.) (case1과 4의 큐와는 다른 큐다!)

-> 키가 있다면 IF문을 탈출해서 맨 하단의 1차원 큐에 넣어지고 방문처리될 것이다!

= 키가 있다는 것은 접근 가능하다는 것이고, 가장자리는 항상 접근 가능하므로 그냥 큐에 넣음으로써 방문한 것으로 처리

※ 위 경우를 생각하지 못해서 몇번 틀렸었다ㅠㅜ

case4. 키가 오는 경우

-> 마찬가지로 인덱스화 시켜서 boolean 배열에 true값을 넣어준다. 그리고 큐에 넣고 방문 여부를 수정한다.

​

2. 키 입력

입력에서 주어지는 기본 키이다.

우선 string으로 입력받고, for문을 이용하여 string을 하나씩 탐색한다.

그리고 key가 "0" 이라면 (= 아무 키도 주어지지 않았다면) 바로 bfs를 시작하고, "0"이 아니라면 기본 키에 대해 처리를 진행해준다.

​

우선 마찬가지로, key를 인덱스화 시켜서 앞서 1번 로직의 case4에서 언급한 boolean 배열 값을 true로 만들어주고, 입력 받은 키와 상호작용하는 문이 2차원 큐에 존재한다면 해당 문의 좌표를 가져온 뒤, 2차원 큐에서 Pop해준다. 그리고 얻은 좌표를 1차원 큐에 넣고 방문 처리를 해준다.

​

즉, 문과 열쇠를 2개의 각기 다른 배열로 관리해주는 것이다.

아래 코드에서, 2차원 큐 door의 0번째 인덱스는 A문이 존재 여부를 의미하고 boolean 배열 keys의 0번째 인덱스는 a키의 습득 여부를 의미하는 것이다!

​

3. bfs

bfs 코드는 1번 2번 로직과 매우 유사하다.

우선 현재 위치가 "$"면 count값을 1 증가시켜주고, 상하좌우 4방향에 대해 탐색을 진행한다.

만약 맵 범위 안에 있고, 벽이 아니고, 방문하지 않았다면 탐색을 진행한다.

​

case1. 문을 만난 경우

-> 키가 있다면 if문을 탈출해서 해당 좌표를 큐에 넣고, 방문 처리를 한다. 키가 없다면 2차원 배열에 해당 좌표를 넣고 continue

case2. 키를 만난 경우

-> 해당 키를 인덱스화시켜서 boolean 배열 값을 true로 만들어준 뒤, 해당 키에 대응되는 잠긴 문이 있다면 문을 열어준다!

(좌표를 큐에 넣는 것 = 탐색 = 문을 연다 = 빈칸으로 만들어준다 // 모두 동일한 뜻이다!)

​

※ 조심해야할 점은 백준에서는 isalpha가 C++ stl과는 return 값이 다르다는 점이고, 문을 제외한 키, 빈칸, 키가 있는 문, $는 모두 큐에 넣어주어야 한다는 점이다!

※ 알파벳 보이면 그냥 크기 26짜리 배열 만들고 생각해보자..ㅋㅋ 거의 대부분 활용되는 듯 하다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<cctype>

using namespace std;

int t,h,w;
char map[101][101];
string key;
bool keys[26];
bool visited[101][101];

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int checkAlpha(char C){
    if(C<='Z' && C>='A') return 1;
    else if(C<='z' && C>='a') return 2;
    else return 0;
}

void bfs( queue<pair<int,int>> q , queue<pair<int,int>> door[26]){
    int cnt=0;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if(map[x][y]=='$')
            cnt++;

        for(int i=0; i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >=0 && nx < h && ny >=0 && ny < w && map[nx][ny]!='*' && !visited[nx][ny]){
                if(checkAlpha(map[nx][ny]) == 1){ // 대문자
                    if(!keys[map[nx][ny]-65]){ // 키가 없다면
                        door[map[nx][ny]-65].push({nx,ny});
                        continue;
                    }
                }
                else if(checkAlpha(map[nx][ny]) == 2) { // 소문자 == 키 습득
                    keys[map[nx][ny] - 97] = true;

                    // 키를 주웠는데 해당 키에 대응되는 잠긴 문이 있다면
                    if(!door[map[nx][ny]-97].empty()) {
                        while (!door[map[nx][ny] - 97].empty()) {
                            int rx = door[map[nx][ny] - 97].front().first;
                            int ry = door[map[nx][ny] - 97].front().second;
                            door[map[nx][ny] - 97].pop();
                            q.push({rx, ry}); // 빈칸으로 바꿔줌 = 해당 위치를 큐에 삽입
                            visited[rx][ry]=true;
                        }
                    }
                }
                // 빈칸, $, 키, 키가 있는 문의 경우는 방문
                q.push({nx,ny});
                visited[nx][ny] = true;
            }
        }
    }
    cout << cnt << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> t;
    while(t--){
        cin >> h >> w;
        queue<pair<int,int>> q;
        queue<pair<int,int>> door[26];
        memset(visited,false,sizeof(visited));
        memset(keys,false,sizeof(keys));

        for(int i=0; i<h;i++){
            for(int j=0; j<w; j++){
                cin >> map[i][j];
                if(i==0 || i == h-1 || j==0 || j==w-1) {
                    if (checkAlpha(map[i][j]) == 1){ // 대문자 == 문
                        if (!(keys[map[i][j] - 65])){ // 키가 없다면
                            door[map[i][j] - 65].push({i, j});
                            continue;
                        }

                    }
                    else if (map[i][j] == '*') continue;
                    else if (checkAlpha(map[i][j]) == 2) { // 소문자 == 키
                        keys[map[i][j]-97] = true;
                    }
                    q.push({i, j});
                    visited[i][j] = true;
                }
            }
        }
        cin >> key;
        if(key != "0"){
            for(char i : key) {
                keys[i - 97] = true;
                if (keys[i - 97] && !door[i - 97].empty()) {
                    while (!door[i - 97].empty()) {
                        int x = door[i - 97].front().first;
                        int y = door[i - 97].front().second;
                        door[i - 97].pop();
                        q.push({x, y});
                        visited[x][y] = true;
                    }
                }
            }
        }
        bfs(q,door);
    }
    return 0;
}