백준 9328번 - 열쇠(C++) 풀이 정리

개요

• 백준, 골드 1, https://www.acmicpc.net/problem/9328
• 풀이 날짜: 2025.2.26.
• 풀이 시간: 10:16~11:37(1시간 21분)
• 알고리즘 분류: 구현, 그래프 탐색 문제
• 사용 언어: C++

문제 해설

해당 문제는 단순히 그래프 탐색을 구현하는 문제이다.

다만 여기서 조사 조건이 여러 개 걸리면서, 따져야 할 상황이 많아지고 있다.

나는 탐색하는 방식을 다음과 같이 결정했다.

1. 모든 테두리에 대해 *이 아닌 곳은 통과가 가능하다.
2. 우선, 탐색할 수 있는 곳을 모두 탐색한다.
   1. 탐색하는 과정에서 모든 문은 열 수 있으면 열고, 아니면 위치를 저장해 놓는다.
   2. 탐색 과정에서 $가 나올 때마다 document 개수를 증가시킨다.
3. 탐색을 완료한 후, 열리지 않은 문을 조사한다.
   1. 열리지 않는 문은 다시 저장해 놓고, 하나라도 문이 열리면 2번 과정으로 돌아가서 순회를 계속 진행한다.

이때 중요한 점은 문에 대해 그에 맞는 키를 찾는 방법이다.

알파벳으로 문과 키가 이루어져 있으므로, 문과 키의 종류는 각각 26개씩이다.

이때 모든 문과 모든 키를 조합해서 맞춰보려고 하면 비효율성이 생기게 된다. 문마다 해당하는 열쇠가 있는지 26번 순회하도록 하면, 연산 비용이 비싸진다.

따라서, 각 키를 가지고 있는지 bool로 저장해 놓고, 문을 발견하면 배열에서 해당 키를 가지고 있는지 index로 조사하도록 한다. 그 규칙은 다음과 같이 정의할 수 있다.

• 발견한 타일을 c라 할 때, c가 문(대문자)이면 (c - ‘A’)가 해당하는 열쇠의 번호가 된다.
• 반면 c가 열쇠(소문자)이면 열쇠 번호는 (c - ‘a’)가 된다.

이런 식으로 문과 열쇠 번호를 매칭하는 함수를 통해, 상수 시간(O(1))에 문에 맞는 키를 찾는다.

코드

과정을 좀 더 나누면 이렇다.

먼저, main에서는 입력을 받는다.

맵은 char 형으로 입력받을 것이다.

#include <iostream>
#include <string>

int h, w;
char map[100][101];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    string keys;

    cin >> t;

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

        for (int i = 0; i < h; i++)
        {
            cin >> map[i];
        }

        cin >> keys;

        cout << SolveMaximumDocs(keys) << '\\n';
    }

    return 0;
}

하나의 맵에 대하여 문제를 해결할 땐 SolveMaximumDocs로 해결한다.

문제를 해결하기 위해서 테두리를 먼저 순회한다. 순회할 땐 dfs 방식으로 순회한다. 이때, 테두리 순회 시에는 이미 방문한 곳(visit = true)은 무시한다.

테두리를 모두 순회한 후에는 현재까지 발견된 잠긴 문을 조사한다. 이는 doorQ라는 이름으로, queue로 관리한다. 각각 좌표를 <row, column> 쌍으로 저장하도록 했다. 그런데, doorQ에 저장된 좌표는 모두 이미 확인한 문이기 때문에 visit 상태가 true일 것이다. 따라서 문을 다시 조사할 땐 visit을 확인하지 않도록 한다.

이때, 순회하면서 모든 문이 잠겨 있을 경우 순회를 멈춰야 한다. 이를 위해 foundWays 변수를 둬서, 하나라도 열려 있을 경우 해당 변수를 true로 설정해서 계속 순회를 진행하도록 한다.

문이 잠겨 있을 경우 다시 doorQ에 해당 위치를 저장해서 다음에 조사하도록 한다.

그런데 여기서 주의할 점은, 문과 열쇠는 열쇠 번호로 변환해서 hasKey에서 열쇠를 갖고 있는지 조사한다는 것이다. 이때 변환하는 식이 다르므로, 그로 인해 혼동성을 줄이기 위해 다음과 같이 함수를 정했다.

• DOOR_KEY: 문(대문자) x에 대해 열쇠 번호 (x - ‘A’)를 구한다.
• KEYIDX: 열쇠(소문자) x에 대해 열쇠 번호 (x - ‘a’)를 구한다.

#include <queue>
#include <cstring>

#define DOOR_KEY(X) (((X) - 'A'))
#define KEYIDX(X) (((X) - 'a'))

bool visit[100][100];
bool hasKey[26];

queue<pair<int, int>> doorQ;

int SolveMaximumDocs(string keys)
{
    int docs = 0;
    
    memset(hasKey, 0, sizeof(hasKey));
    memset(visit, 0, sizeof(visit));

    if (keys[0] != '0')
    {
        for (char c : keys)
        {
            hasKey[KEYIDX(c)] = true;
        }
    }

    // 입구 조사
    doorQ = queue<pair<int, int>>();
    
    for (int j = 0; j < w; j++)
    {
        if (!visit[0][j])
            docs += dfs(0, j);
        if (!visit[h-1][j])
            docs += dfs(h-1, j);
    }
    for (int i = 1; i < h - 1; i++)
    {
        if (!visit[i][0])
            docs += dfs(i, 0);
        if (!visit[i][w - 1])
            docs += dfs(i, w - 1);
    }

    // 문 조사하기
    bool foundWays;
    do
    {
        foundWays = false;
        // 문에 해당하는 키가 있으면 들어갈 수 있다(visit이어도 통과)
        int qsize = doorQ.size();
        for (int i = 0; i < qsize; i++)
        {
            int row = doorQ.front().first;
            int col = doorQ.front().second;
            doorQ.pop();

            if (hasKey[DOOR_KEY(map[row][col])])
            {
                foundWays = true;
            }
            docs += dfs(row, col);
        }
    } while (foundWays);

    return docs;
}

실제 순회는 dfs에서 진행한다.

깊이 우선 탐색을 사용하면, 맵의 크기가 100x100이므로 최악의 경우 깊이가 10000까지 달하게 된다. 그 때문에 너무 깊이가 깊어서 오류가 생길 위험이 있었는데, 다행히 BFS를 사용하지 않고도 문제가 해결되었다.

순회할 때 확인하는 조건은 이렇다.

• 벽이면 무시
• 문인데 잠겨 있을 경우 doorQ에 삽입하고 종료
• 그 외의 경우 탐색 진행
• 이때 열쇠이면 hasKey를 true로 설정하여 열쇠 소유 여부를 설정
• $를 발견하면 document 개수를 증가시킴

특히나 이 코드를 짜면서 생각해야 했던 점은, 코드의 복잡도를 최대한 줄이면서 어떻게 dfs를 짜는지였다.

문제가 복잡하기 때문에, 코드 짤 때 실수를 해서 푸는 시간이 길어지는 것이 가장 문제가 될 것 같았다.

그러니 최대한 중복된 코드를 줄이기 위해서, 문 확인 작업, 열쇠 획득, 문서($) 획득 등의 모든 탐색 과정은 각 노드를 방문할 때 처리하도록 했다.

int dir_x[4] = { 0, -1, 1, 0 };
int dir_y[4] = { -1, 0, 0, 1 };

int dfs(int row, int col)
{
    // 벽이면 무시
    int docs = 0;
    if (map[row][col] == '*')
        return 0;
    visit[row][col] = true;
    // 문인데 잠겨 있을 경우 킵
    if (map[row][col] >= 'A' && map[row][col] <= 'Z' &&
        hasKey[DOOR_KEY(map[row][col])] == false)
    {
        doorQ.push(make_pair(row, col));
        return 0;
    }
    // 문이 아닐 경우 진행
    if (map[row][col] >= 'a' && map[row][col] <= 'z')
    {
        hasKey[KEYIDX(map[row][col])] = true;
    }
    else if (map[row][col] == '$')
        docs++;

    for (int dir = 0; dir < 4; dir++)
    {
        int nextRow = row + dir_y[dir];
        int nextCol = col + dir_x[dir];

        if (nextRow < 0 || nextRow >= h ||
            nextCol < 0 || nextCol >= w)
            continue;
        if (visit[nextRow][nextCol])
            continue;
        docs += dfs(nextRow, nextCol);
    }

    return docs;
}

전체 코드는 아래 링크에서 확인할 수 있다.

https://github.com/Nicitis/Problem-Solving/blob/main/2025/02/20250226/9328.cpp