[백준 9328] 열쇠

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

알고리즘의 묘미랄까.. 다 풀고 남들의 코드를 보는데 나와 다른 부분이 있어 흥미로웠다.

1. 시작 지점을 구하는 방법
   • 내 방법: 입력을 받으며 테두리일 경우 '.'인 경우 따로 저장
   • 찾은 방법: '.'으로만 이루어진 테두리를 하나 만들어 감싼다.
     예) (3,3)이 있다면, (4,4)로 만들고 테두리들을 모두'.'으로 채운다
2. 잠긴 문을 만났을 때, 어떻게 할 것인가
   • 내 방법: 일단 스탑하고, 열쇠를 만난다면 그동안의 visited를 초기화 하고 다시 시작한다.
   • 찾은 방법: 따로 저장해 뒀다가 열쇠를 찾으면 저장해 뒀던 것을 큐에 옮긴다.

즉, 내 알고리즘의 시간복잡도는 최악의 경우 키의 개수인 26 * 맵의 크기인 nm 이었고, 찾은 방법은 최악의 경우 nm이었다. 결국 상수곱이므로 크게 차이는 나지 않지만, 그래도 좀 더 좋은 알고리즘이 있다면 그 방법을 택하는게 좋은거니 찾은 방법을 기준으로 서술하겠다.

풀이 과정

1. 테두리를 '.'으로 채운 뒤 (1,1)부터 값을 입력 받는다.
2. 테두리를 시작 값으로 bfs를 실행한다. 만약 '$'를 찾으면 cnt를 증가시킨다.
3. 만약 문이 잠겨 있다면 queue[알파벳 번호]에 문의 좌표를 저장해 둔다.
4. 만약 키를 찾았다면 queue[알파벳 번호]에 저장되어 있던 좌표들을 bfs에 꺼낸다.
5. bfs 큐가 빌 때까지 반복한다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>  
using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        //map과 visited 초기화
        char map[102][102];  
        bool visited[102][102]; 
        memset(visited, false, sizeof(visited)); 
        memset(map, '.', sizeof(map));  
        
        //map 입력 - 테두리를 제외해 1부터 n까지에 채운다
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> map[i][j];
            }
        }


        // Key 설정
        string key;
        cin >> key;
        bool keyArr[26] = {false};
        if (key != "0") {
            for (char c : key) {
                keyArr[c - 'a'] = true;
            }
        }
        
        // BFS 
        int move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        queue<pair<int, int>> q;
        queue<pair<int, int>> door[26];
        
        q.push({0,0});
        visited[0][0] = true;

        int cnt = 0;
        while (!q.empty()) {
            int i = q.front().first;
            int j = q.front().second;
            q.pop();

            for (auto& mv : move) {
                int mi = i + mv[0];
                int mj = j + mv[1];
                if (mi < 0 || mi > n+1 || mj < 0 || mj > m+1) continue;
                if (map[mi][mj] != '*' && !visited[mi][mj]) {
                    char next = map[mi][mj];
                    if (next == '$') {
                        cnt++;
                    }
                    else if ('A' <= next && next <= 'Z') { // 문을 만날 경우
                        if (!keyArr[next - 'A']) {  // 키가 존재하지 않을 경우
                            door[next - 'A'].push({mi, mj}); 
                            continue;  
                        }
                    }
                    else if ('a' <= next && next <= 'z') { // 키를 만날 경우
                        if (!keyArr[next - 'a']) {
                            keyArr[next - 'a'] = true;
                            while (!door[next - 'a'].empty()) {
                                q.push(door[next - 'a'].front());
                                door[next - 'a'].pop();
                            }
                        }
                    }

                    q.push({mi, mj});
                    visited[mi][mj] = true;
                }
            }
        }

        cout << cnt << '\n'; 
    }

    return 0;
}

참고
https://yabmoons.tistory.com/97