鍵(白駿9328号)

(ソース)https://www.acmicpc.net/problem/9328

📖 概要

マッピングにドア、キー、ドキュメント、壁の位置が表示されている場合は、マッピングで取得できるドキュメントの合計数を返す必要があります.
この問題を厄介にする1つの条件は,地図上で新しい鍵を得ることができ,新しく鍵を手に入れると,その瞬間に移動する地図範囲が変化することである.したがって、DFSを使用してナビゲートする場合は、キーがないため再アクセスできないパスを任意の方法で記録する必要があります.
DFSで問題を解決したいのですが、鍵を拾った瞬間にドアを開ける方法を思いつきました」と話しています.(空の空間)に変える方法.その後変更されたマッピングでDFSを再起動します.(正確には、HashTableに新しい鍵を登録し、DFSを再起動する)
すなわち,ゲートで塞がれて近づけない経路を別途記録する方式ではなく,鍵を取得するたびに地図を変更した後,いっそ空白の状態でDFSを再回転させる方式である.
しかし、今私は書きながら、私の表現方法には効率の悪い面があると思っています.新しいDFSを返すたびに、新しいオープンパスだけを返すのは当然有効です.
検索中にHashTableに登録されているドアに対応する鍵が得られた瞬間に、新たなスタートポイントを追加してDFSを回転させる方式を追加すれば、より効果的に問題を解決することができる.

時間の複雑さ

鍵を拾った瞬間、該当するドア」.このプロシージャを最初から(空き領域)に置き換えて繰り返す場合、最悪の場合、マッピングに存在するノード数で繰り返すことになります.幸いなことに,入力マッピングの範囲は大きくないため,ノードの最大数は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;
}