백준 9328 열쇠

비트마스킹 문제를 푸려고 보는 중, 내가 분명히 풀었던건데 비트마스킹을 쓴 기억이 없어 들고와봤다. 내가 풀었을때는, BFS 탐색을 조금 예외상황을 넣으며 풀었다. 

 

처음 접근할때는, 맵을 곧이곧대로 입력받고 시작 점을 하나 잡아서 구현했었다. 이 경우 벽이 아닌곳을 통해 다른곳으로 이동하는 경우 처리가 너무 빡셌다. 그래서 그냥 맵 주변을 전부 접근가능한 . 로 표시하는 방법을 선택했다. 이 경우, 자연스럽게 BFS탐색으로 해당 케이스가 커버된다.

맵 입력을 받은 뒤, 열쇠 리스트를 입력으로 받아 해당 열쇠로 열 수 있는 문을 전부 갈 수 있는 '.'로 대체해준다. 열쇠 입수 순간에 맵에 표시를 한다는 생각은 차마 못했는데, 다른 솔루션에서 봤다. 입수 키 리스트를 들고, 문을 볼때마다 키 리스트와 대조해 진행여부를 판단하는 것은 너무 복잡도가 올라가는 구현이었다.

이후 BFS로 탐색을 한다. 탐색을 하며 문서를 만나면 입수 문서 수를 늘리고, 그 문서가 있던 자리를 '.'로 변경하며 계속 탐색을 한다. 만약, 열쇠를 입수하게 되면, 그 열쇠로 잠겨있던 문을 열고('.'로 표시) visited[][]배열을 초기화한다. 이 visited[][] 배열의 초기화 아이디어를 떠올리는게 어려웠다. 문으로 잠겨있던 곳을 다시 가려면 visited[][]로 이미 표시되어 있는 곳을 가야하므로 이 과정이 꼭 들어가야 한다...

 

그 과정을 진행하면! 답을 구할 수 있다...

---

#include <iostream>
#include <queue>
#include <string.h>

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct cur{
    int x;
    int y;
    bool key[26];
    int paperCnt;
    int keyCnt;
    cur (int y, int x, int cnt) : y(y), x(x), paperCnt(cnt) {}
    void setKey(bool keylist[])
    {
        for (int i = 0; i < 26; i ++)
        {
            this->key[i] = keylist[i];
            if (keylist[i])
                keyCnt++;
        }
    }
};

int main()
{
    int T;
    std::cin >> T;

    for (int Tcase = 0; Tcase < T; Tcase++)
    {
        int N, M;
        std::cin >> N >> M;
        std::string map[N+2]; //지도
        int visited[N+2][M+2]; //방문여부 체크
        bool key[26];

        memset(visited, 0, sizeof(visited));
        memset(key, 0, sizeof(key));
        for (int i = 0 ; i < N + 2; i ++)
            map[i].clear();
        for (int i = 0; i < M + 2; i++)
            map[0] += '.';
        for (int i = 1; i <= N; i++)
        {
            std::string inp;
            std::cin >> inp;
            map[i] += '.';
            map[i] += inp;
            map[i] += '.';
        }
        for (int i = 0; i < M + 2; i++)
            map[N+1] += '.';
        std::string keyList;
        std::cin >> keyList;
        std::queue<cur> Q;
        if (keyList[0] != '0') //소유하고 있는 열쇠들 문 전부 열어두기('.' 으로 바꾸기.)
        {
            for (int i = 0; i < keyList.size(); i++)
            {
                key[keyList[i] - 'a'] = true;
                for (int y = 1; y <= N; y++)
                {
                    for (int x = 1; x <= M; x++)
                    {
                        if (map[y][x] == (char)std::toupper(keyList[i]))
                            map[y][x] = '.';
                    }
                }
            }
        }
        // 맵 가장자리가 아니라 시작점 일일히 찾았던 코드 로직 흔적.
        // for (int i = 0; i < M; i++)
        // {
        //     if (map[0][i] != '*')
        //     {
        //         cur now(0, i, 1);
        //         now.setKey(initKeylist);
        //         if ('a' <= map[0][i] && map[0][i] <= 'z')
        //             now.key[map[0][i] - 'a'] = true;
        //         Q.push(now);
        //     }
        //     if (map[N-1][i] != '*')
        //     {
        //         cur now(N-1, i, 1);
        //         now.setKey(initKeylist);
        //         if ('a' <= map[N-1][i] && map[N-1][i] <= 'z')
        //             now.key[map[N-1][i] - 'a'] = true;
        //         Q.push(now);
        //     }
        // }
        // for (int i = 0; i < N; i++)
        // {
        //     if (map[i][0] != '*')
        //     {
        //         cur now(i, 0, 1);
        //         now.setKey(initKeylist);
        //         if ('a' <= map[i][0] && map[i][0] <= 'z')
        //             now.key[map[i][0] - 'a'] = true;
        //         Q.push(now);
        //     }
        //     if (map[i][M-1] != '*')
        //     {
        //         cur now(i, M-1, 1);
        //         now.setKey(initKeylist);
        //         if ('a' <= map[i][M-1] && map[i][M-1] <= 'z')
        //             now.key[map[i][M-1] - 'a'] = true;
        //         Q.push(now);
        //     }
        // }
        //std::cout << " ";

        /*
        BFS 로직 짤 때, 현재 위치 받아서 visited 체크및 처리 후 탐색 vs 현재 위치 받아서 다음것 탐색 + visited 체크 차이.
        */
        Q.push(cur(0,0,0));
        int docs = 0;
        while(!Q.empty())
        {
            cur now = Q.front(); Q.pop();
            int nx = now.x ;
            int ny = now.y ;

            if (nx < 0 || nx > M + 1 | ny <0 || ny > N+1 || map[ny][nx] == '*' || ('A' <= map[ny][nx] && map[ny][nx] <= 
            'Z') || visited[ny][nx])
                continue;
            visited[ny][nx] = true;

            if (map[ny][nx] == '$')
            {
                now.paperCnt++;
                docs++;
                map[ny][nx] = '.';
            }            

            if ('a' <= map[ny][nx] && map[ny][nx] <= 'z')
            {
                char door = (char)std::toupper(map[ny][nx]);
                map[ny][nx] = '.';

                if (key[door - 'A'] == false)
                {
                    key[door - 'A'] = true;
                    for (int y = 1; y <= N; y++)
                    {
                        for (int x = 1; x <= M; x++)
                        {
                            if (map[y][x] == door)
                                map[y][x] = '.'; // 해당 키로 잠긴 문 열어두기('.'로 바꾸기)
                        }
                    }
                }
                //잠긴 문이 열렸으므로, 모든 경로 다시 확인 필요.
                memset(visited, false, sizeof(visited));
                while(!Q.empty())
                    Q.pop();
                Q.push(cur(ny, nx, now.paperCnt));
            }
            //동서남북 탐색

            for(int i = 0; i < 4; i++)
            {
                int nextX = nx + dx[i];
                int nextY = ny + dy[i];
                Q.push(cur(nextY, nextX, now.paperCnt));
            }
                // 탐색 조건 추가. 키 다 찾기 전에는 visit 표시 안하고, 탐색 다 하면 visit 표시하면서 탐색 X -> 저번 구현때 시도했지만 현 구현에서는 필요없음
        }
        std::cout <<  docs << '\n';
    }
}

Bitmask 구현도 알아봤다. Bitmask 쓴다고 좀 기대했었는데, 그냥 현재 가지고 있는 키 상황을 int변수로 저장하는게 다였다... 그래도 처음 내가 접근했던 방식인 문 만날때 키 확인을 bitmask 방식으로 구현하면 조금 간략해지는것 같다. Bitmask 솔루션은 여기서 봤다.

 

오늘도 평온한 하루가 되길. 슨민.