백준 9328번 열쇠 C++ (골드1)

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

 

크게 보면 단순 bfs 구현 문제인데, 어떤 열쇠가 있어야 특정 문을 열 수 있고, 맵 밖으로 나갔다고 끝이 아니라 다른 외곽 지역으로 들어올 수 있다는 추가 조건이 있는 문제이다.

 

우선 방문 표시를 할때 단순히 true, false로 표시하면 안된다.

어떤 열쇠를 보유하지 않고 특정 문에 도달했을때와 보유한 상태에서 도달했을 때 차이가 있기 때문이다.

그래서 비트연산을 이용해서 어떤 열쇠들을 가진 상태로 방문했는지를 표시하였다.

예를들어 a열쇠와 c열쇠가 있다면 101(cba)이고 10진수로 변환하면 5가 된다.

이렇게 하면 정수 하나로 어떤 열쇠들을 가지고 방문했는지 표시할 수 있다.

 

그리고 어떤 열쇠를 가지고 있는지 확인할 수 있어야 한다.

보유한 열쇠들도 위와 마찬가지로 비트연산을 통해 저장하였고, 이렇게 하면 문에 도달했을때 해당 문을 여는데 필요한 열쇠와 보유한 열쇠들을 or연산을 통해 문을 열 수 있는지 확인할 수 있다.

 

이후에는 bfs길찾기 문제처럼 해결하면 되고, 만약 다음에 도달할 좌표가 맵 밖으로 나가게 된다면 다시한변 외곽을 조사하여 큐에 넣어준다.

 

사실 삽질을 좀 할 줄 알았는데 한번에 통과되어서 다행이었다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int r, c;
int myKeyBit = 0;
int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;
vector<vector<char>> board;
vector<vector<int>> found;

void AddKey(char key)
{
    int keyNum = key - 'a';
    myKeyBit |= (1 << keyNum);
}

bool HaveKey(char key)
{
    int keyNum = key - 'a';
    bool haveKey = ((1 << keyNum) & (myKeyBit));
    return haveKey;
}

bool CanGo(int row, int col)
{
    // 벽이면 못감
    if (board[row][col] == '*') return false;
    // 빈공간/문서가 있는 공간이면 갈수있음
    if (board[row][col] == '.' || board[row][col] == '$') return true;
    // 열쇠가 있는 공간이면 갈수있음
    if (board[row][col] >= 'a' && board[row][col] <= 'z') return true;

    // 문이면 열쇠가 있으면 갈수있음
    char door = board[row][col];
    char requiredKey = tolower(door);
    if (HaveKey(requiredKey)) return true;
    return false;
}

// 외곽지역들 갈 수 있는지 검사하여 큐에 넣어준다.
void PushEntrancePos() {
    for (int i = 0; i < r; i++)
    {
        if (CanGo(i, 0))
        {
            if (found[i][0] != myKeyBit)
            {
                q.push({ i,0 });
                found[i][0] = myKeyBit;
            }
        }
        if (CanGo(i, c - 1))
        {
            if (found[i][c - 1] != myKeyBit)
            {
                q.push({ i,c - 1 });
                found[i][c - 1] = myKeyBit;
            }
        }
    }
    for (int i = 0; i < c; i++)
    {
        if (CanGo(0, i))
        {
            if (found[0][i] != myKeyBit)
            {
                q.push({ 0,i });
                found[0][i] = myKeyBit;
            }
        }
        if (CanGo(r - 1, i))
        {
            if (found[r - 1][i] != myKeyBit)
            {
                q.push({ r - 1,i });
                found[r - 1][i] = myKeyBit;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin >> t;
    while (t--)
    {
        int ans = 0;
        cin >> r >> c;
        board = vector<vector<char>>(r, vector<char>(c));
        found = vector<vector<int>>(r, vector<int>(c, -1));
        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                cin >> board[i][j];
            }
        }
        string initialKeys;
        cin >> initialKeys;

        if (initialKeys != "0")
        {
            for (int i = 0; i < initialKeys.length(); i++)
            {
                char key = initialKeys[i];
                AddKey(key);
            }
        }

        PushEntrancePos();

        while (!q.empty())
        {
            auto a = q.front();
            q.pop();
            if (board[a.first][a.second] == '$')
            {
                // 문서가 있다면 훔친 문서의 개수를 1 증가시키고 해당 공간을 빈 공간으로 밀어준다.
                board[a.first][a.second] = '.';
                ans++;
            }

            if (board[a.first][a.second] >= 'a' && board[a.first][a.second] <= 'z')
            {
                // 열쇠가 있다면 열쇠를 주워서 보유한 열쇠를 나타내는 비트에 해당 열쇠를 추가하고 빈 공간으로 밀어준다.
                AddKey(board[a.first][a.second]);
                board[a.first][a.second] = '.';
            }

            // 현재 위치에서 상하좌우 검사
            for (int i = 0; i < 4; i++)
            {
                int nextRow = a.first + dRow[i];
                int nextCol = a.second + dCol[i];
                if (nextRow < 0 || nextRow >= r) {
                    // 밖으로 나가게 된다면 외곽 지역들을 검사하여 갈 수 있는 공간들을 큐에 넣어준다.
                    PushEntrancePos();
                    continue;
                }
                if (nextCol < 0 || nextCol >= c) {
                    // 밖으로 나가게 된다면 외곽 지역들을 검사하여 갈 수 있는 공간들을 큐에 넣어준다.
                    PushEntrancePos();
                    continue;
                }
                // 다음 공간으로 갈 수 있고 현재 열쇠들을 가진 상태로 아직 방문하지 않았다면 큐에 넣어주고 방문 표시를 해준다.
                if (CanGo(nextRow, nextCol) && found[nextRow][nextCol] != myKeyBit) {
                    q.push({ nextRow,nextCol });
                    found[nextRow][nextCol] = myKeyBit;
                }
            }
        }
        cout << ans << "\n";
        myKeyBit = 0;
    }
}