열쇠 (백준 9328번)

(출처) https://www.acmicpc.net/problem/9328

📖 개요

문,열쇠,문서,벽에 대한 위치가 표시된 맵이 입력으로 주어질 때, 해당 맵에서 구할 수 있는 총 문서의 개수를 구해서 리턴해줘야 하는 문제.

해당 문제를 까다롭게 만드는 조건 중 하나는 맵에서 새로운 열쇠를 획득할 수 있다는 것인데 열쇠를 새로 획득하면 그 순간 움직일 수 있는 맵의 범위가 바뀌게 된다. 따라서 만약 DFS로 탐색을 진행하고자 한다면 열쇠가 없어서 더 이상 접근하지 못했던 경로를 어떠한 방식이로든 기록해 주어야한다.

DFS로 문제를 해결하고자 했고 어떤 방법으로 구현해야 할지 내가 떠올렸던 방법은 열쇠를 줍는 순간 해당하는 문을 '.'(빈공간)으로 바꿔주는 방식이었다. 이후 변경된 맵에서 다시 새롭게 DFS를 돌린다. (정확하게는 HashTable에 새로운 key를 등록한 후 다시 DFS 돌리는 방식)

즉 문에 막혀 접근하지 못했던 경로를 따로 기록하는 방식을 택하지 않았고 열쇠를 획득할 때마다 맵을 변경 후 아예 백지상태에서 다시 DFS를 돌리는 방식을 택했다.

그런데 지금 글을 쓰면서 생각해 보니 내가 구현한 방식은 비효율적인 측면이 보인다. 매번 DFS를 새로 돌려주는 것보다는 새롭게 열린 경로만 DFS 돌리는 것이 당연히 효율적이니까.

문에 막혀 접근하지 못했던 좌표를 HashTable에 기록하고(key는 Key로 value는 좌표로) 만약 탐색 중 HashTable에 등록된 문에 맞는 열쇠를 획득하는 순간, 해당 좌표를 새로운 스타트포인트 추가하여 DFS를 추가적으로 돌리는 식으로 진행했다면 훨씬 효율적으로 문제를 구현했을 것 같다.

⚙ 시간복잡도

열쇠를 줍는 순간 해당하는 문을 '.'(빈공간)으로 바꿔서 처음부터 다시 과정을 반복해나가는 방법의 경우, Worst Case는 맵에 존재하는 노드의 수만큼 과정이 반복되는 것이다. 다행히도 입력으로 들어오는 맵의 범위가 그리 크지 않기 때문에 노드의 최대 갯수는 1만 개 정도밖에 안된다.

즉 최악의 경우 1만 번의 반복이 예상되는데, 각 반복마다 DFS 함수가 새롭게 실행되므로 1만 * DFS 함수의 반복 횟수가 WorstCase의 총 반복 횟수가 될 것이다.

상하좌우로(4개의 간선) 움직일 수 있는 1만 칸의 맵을 DFS 돌리는 경우 약 4만 번의 반복이므로 (DFS 시간복잡도 == O(N+E)), WorstCase의 총 반복 횟수는 1만 * 4만 = 4억 정도이다.

시간제한은 1초 정도로 아슬아슬하긴 하지만 해당 방식으로도 문제를 해결할 수 있어 보였다.

✨ 코드

#include <vector>
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;
vector<vector<char>> map;
vector<pair<int,int>> startPoint;
vector<vector<bool>> visited;
unordered_map<char,int> keys;
int h,w;
int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; //상하좌우순

bool dfs(int currentY, int currentX, int &result) {
    //방문한 정점 체크표시
    visited[currentY][currentX] = true;
    //현재칸에 열쇠 혹은 문서가 있는지 확인
    if(map[currentY][currentX] == '$') {
        result++; //문서획득
        map[currentY][currentX] = '.';
    }
    else if(map[currentY][currentX] >= 97 && map[currentY][currentX] <= 122) {
        char key = map[currentY][currentX];
        keys[key] = 1; //열쇠획득. 새로운 열쇠 획득시 처음 입구에서부터 다시 dfs를 돌려야한다
        map[currentY][currentX] = '.';
        return true;
    }
    //다음칸으로 이동
    for(int i = 0; i < 4; i++) {
        int nextY = currentY + direction[i][0];
        int nextX = currentX + direction[i][1];
        if(nextY < 0 || nextY >= h || nextX < 0 || nextX >= w) continue; //맵밖으로 나간 경우 Pass
        if(visited[nextY][nextX]) continue; //이미 방문한 노드인 경우 Pass
        if(map[nextY][nextX] != '.') {
            if(map[nextY][nextX] == '*') continue; //벽에 막힌 경우 처리
            if(map[nextY][nextX] >= 'A' && map[nextY][nextX] <= 'Z') { //해당 위치가 문인데 열쇠가 없는 경우 Pass
                char lowerCase = map[nextY][nextX] + 32;
                if(keys.find(lowerCase) == keys.end()) continue;
            }
        }

        if(dfs(nextY,nextX, result)) return true; //dfs 도중 새로운 열쇠를 획득한 적 있는 경우. 새롭게 dfs를 시작해야하므로 즉시 return해서 탐색을 종료.

    }
    return false;
}

int main(){
    int T;
    cin >> T;
    while(T-- != 0) {
        //맵등록
        cin >> h >> w;
        map = vector<vector<char>> (h, vector<char>(w,'*'));
        startPoint = vector<pair<int,int>>();
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                cin >> map[i][j] ;
            }
        }
        //key를 hashTable(keys)에 등록
        string keyString;
        cin >> keyString;
        if(keyString == "0") keyString = "";
        keys = unordered_map<char,int>();
        for(int i = 0; i < keyString.size(); i++) keys[keyString[i]] = 1;

        int result = 0;
        bool isNewKey = true;
        while(isNewKey) {
            visited = vector<vector<bool>>(h, vector<bool>(w, false));
            isNewKey = false;
            //스타트포인트를 찾기위해 전체 맵을 1번 순회
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) {
                    //dfs를 돌릴 수 있는 시작점(startPoint)을 등록
                    if((i == 0 || i == h-1 || j == 0 || j == w-1) && map[i][j] != '*') {
                        if(map[i][j] >= 'A' && map[i][j] <= 'Z') {
                            char lowerCase = map[i][j] + 32;
                            if(keys.find(lowerCase) == keys.end()) continue;
                        }
                        startPoint.push_back(pair<int,int>(i,j));
                    }
                }
            }
            //dfs시작
            for(int i = 0; i < startPoint.size(); i++) {
                //아직 방문하지 않은 스타트포인트부터 방문하면서 DFS를 시작
                if(visited[startPoint[i].first][startPoint[i].second] == false ) {
                    isNewKey = dfs(startPoint[i].first, startPoint[i].second, result);
                }
                if(isNewKey) break;
            }
        }
        cout << result << endl;
    }
    return 0;
}