[백준 9328] 열쇠

 

그래프 탐색 문제로 DFS나 BFS 등으로 풀 수 있다. 열쇠 처리를 구현 해주어야 하는데, 종류가 알파벳의 갯수인 26가지로 한정되어 있으므로 bool 배열을 이용해도 되고, 비트마스킹을 이용해도 된다. 나는 비트마스킹을 이용했다.

 

 일단 일반적인 그래프 탐색 문제랑은 조금 다르게 빌딩의 밖에서 시작하고, 가장자리를 통해 빌딩 안팎을 드나들 수 있다는 조건이 추가로 붙어있다. 따라서 입력 받을 때에 입구 정보를 따로 저장해두고 이를 이용할 수 있게 하는 것이 효율적이다. 그 다음에는 평범하게 탐색을 진행한다. 내 경우에는 스택과 DFS를 사용해서 탐색을 진행했다.

 탐색 과정에서 가장 먼저 해야하는 것은 방문 여부 검사이다. 나는 이를 위해 처음에는 XOR 연산을 이용하려 했다. 그렇게 하면 현재 열쇠 보유 상태와 방문 여부를 저장해둔 값을 비교해서 다르면 true가 떨어지기 때문이다. 근데 조금 생각해보니, 만약 열쇠 a b c를 보유한 채로 방문한 이력이 있는 노드를 열쇠 a c를 들고 왔을 때 방문할 필요가 있나 하는 생각이 들었다. XOR 연산을 이용한다면 서로 다른 비트가 존재하기 때문에 true가 리턴되고 불필요한 탐색을 추가적으로 하게 될 것이다. 그리고 이는 방문 여부 값이 갱신되고, 이전에 스택에 들어온 값이 다시 그 값을 갱신하고를 반복하며 무한루프에 빠질 수 있었다.

 그래서 나는 기존 방문 이력 값에 현재 열쇠 보유 상태를 OR 연산하고 이를 기존 방문 이력 값과 같은지 확인하도록 했다.

이렇게 하면 기존 방문 이력과 비교했을 때 추가적으로 획득한 열쇠가 있을 때만 판별해낼 수 있다.

 

 그렇게 현재 방문한 곳에 지금과 같은 열쇠 보유 상태로 방문한 적 없다면 현재 방문 한 곳이 문인지 확인한다. 만약 문이라면 열쇠가 없다면 해당 노드를 방문할 수 없으므로, 현재 열쇠 상태에서 AND 연산으로 문에 대응되는 열쇠가 있는지 확인해준다. 없다면 스택의 top을 꺼내는 단계로 돌아가고, 있다면 탐색을 이어간다.

 이후에는 현재 방문한 곳에 훔쳐야 하는 문서가 있는지 확인하고 있다면 획득 결과 값을 1 증가시키고, 해당 노드에는 '.'을 대입해서 이후 중복 연산을 막아준다. 그리고 문서도 아니라면 열쇠가 있는지 확인해서, 열쇠라면 현재 열쇠 상태에 OR 연산으로 획득처리 해준다.

 

 위의 방문 노드 확인 과정이 끝나면 방면 여부 값을 현재 열새 상태와 OR 연산을 통해 갱신해준다. 다음으로는 상하좌우 방향에 대해 방문검사를 하고 방문하지 않았다면 스택에 넣어준다. 상하좌우를 탐색하는 과정에서 주어지는 빌딩의 범위를 벗어나는 경우라면 밖으로 나간 경우로 상정하고, 처음에 만들어둔 입구 배열을 하나씩 확인하며 방문검사를 하고 방문하지 않았다면 스택에 넣어준다. 이를 반복하면 DFS가 끝났을 때 획득한 문서가 결과 값에 저장되어있고, 위 모든 과정을 모든 테스트 케이스에 대해 반복한다.

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

typedef pair<int, int> point;

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

int main() {
    int t, h, w;
    cin >> t;

    char matrix[100][100];

    for(int tc=0; tc<t; tc++) {
        cin >> h >> w;

        vector<point> entranceList; // {y, x}

        for(int i=0; i<h; i++) {
            for(int j=0; j<w; j++) {
                cin >> matrix[i][j];

                if((i==0||j==0||i==h-1||j==w-1)&&matrix[i][j]!='*') {
                    entranceList.push_back({i, j});
                }
            }
        }

        int keySave = 1; // 000..001(2) : 열쇠 없이 탐색하는 케이스
        string keyInput;
        cin >> keyInput;
        if(keyInput!="0") {
            for(auto c : keyInput) {
                keySave = keySave | 1<<(c-'a'+1);
            }
        }

        stack<pair<point, int> > st;
        for(auto p : entranceList) {
            st.push({p, keySave});
        }

        vector<vector<int> > isVisited = vector<vector<int> >(h, vector<int>(w, 0));
        int result = 0;
        while(!st.empty()) {
            point curPoint = st.top().first;
            int curKey = st.top().second;
            st.pop();

            if((isVisited[curPoint.first][curPoint.second] | curKey) != isVisited[curPoint.first][curPoint.second]) {
                char curChar = matrix[curPoint.first][curPoint.second];

                if(isupper(curChar) && (curKey & 1<<(curChar-'A'+1))==0) {
                    continue;
                } else if(matrix[curPoint.first][curPoint.second] == '$') {
                    result++;
                    matrix[curPoint.first][curPoint.second] = '.';
                } else if(islower(matrix[curPoint.first][curPoint.second])) {
                    curKey = curKey | 1<<(matrix[curPoint.first][curPoint.second]-'a'+1);
                }

                isVisited[curPoint.first][curPoint.second] = isVisited[curPoint.first][curPoint.second] | curKey;
                
                for(int i=0; i<4; i++) {
                    int targetY = curPoint.first+dy[i];
                    int targetX = curPoint.second+dx[i];
                    if(targetY>=0 && targetY<h && targetX>=0 && targetX<w) {
                        if(matrix[targetY][targetX]!='*' && ((isVisited[targetY][targetX] | curKey) != isVisited[targetY][targetX]) ) {
                            st.push({{targetY, targetX}, curKey});
                        } 
                    } else {
                        for(auto p: entranceList) {
                            if((isVisited[p.first][p.second] | curKey) != isVisited[p.first][p.second]) {
                                st.push({{p.first, p.second}, curKey});
                            }    
                        }
                    } 
                }

            }
        }

        cout << result << "\n";
    }
}