[백준/Baekjoon] 9328 열쇠 C++ :: BFS

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

9328번: 열쇠

---

1. Logic

방에 들어갈 때 .이나 $이면 들어갈 수 있기 때문에 방 주변을 이동 가능한 공간으로 둘러싸서 입구를 찾아준다.

BFS함수 안에서 각 열쇠마다 키가 없을 때 방문했던 좌표를 queue에 저장해놓고 키를 찾으면 queue에서 뽑았던 좌표를 빼서 확인해준다.

아이디어가 신박했다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

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

int h, w;

char room[102][102];
bool vis[102][102];
bool key[26];

int bfs() {
    queue<pair<int, int>> q;
    queue<pair<int, int>> keyDir[26];
    
    int ans = 0;
    
    q.push({0, 0});
    vis[0][0] = true;
    
    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        
        q.pop();
        
        if(room[y][x] == '$') ans++;
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx > w+1 || ny > h+1) continue;
            if(room[ny][nx] == '*') continue;
            if(vis[ny][nx]) continue;
            
            if(room[ny][nx] >= 'A' && room[ny][nx] <= 'Z') {
                int keyNum = room[ny][nx]-'A';
                if(key[keyNum]) {
                    vis[ny][nx] = true;
                    q.push({ny, nx});
                }
                else {
                    keyDir[keyNum].push({ny, nx});
                }
            }
            else if(room[ny][nx] >= 'a' && room[ny][nx] <= 'z') {
                int keyNum = room[ny][nx]-'a';
                
                vis[ny][nx] = true;
                key[keyNum] = true;
                q.push({ny, nx});
                
                while(!keyDir[keyNum].empty()) {
                    q.push(keyDir[keyNum].front());
                    keyDir[keyNum].pop();
                }
            }
            else {
                vis[ny][nx] = true;
                q.push({ny, nx});
            }
        }
    }
    
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while(t--) {
        memset(room, '.', sizeof(room));
        memset(vis, false, sizeof(vis));
        memset(key, false, sizeof(key));

        cin >> h >> w;
        
        for(int i = 1; i <= h; i++) {
            for(int j = 1; j <= w; j++) {
                cin >> room[i][j];
            }
        }
        
        string k;
        cin >> k;
        
        if(k != "0") {
            for(int i = 0; i < k.size(); i++) {
                key[k[i]-'a'] = true;
            }
        }
        
        cout << bfs() << "\n";
    }
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐