[백준] 9328 - 열쇠
[Gold I] 열쇠 - 9328
성능 요약
메모리: 35036 KB, 시간: 108 ms
분류
구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 격자 그래프
제출 일자
2026년 4월 26일 10:13:18
문제 설명
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
- '.'는 빈 공간을 나타낸다.
- '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
- '\$'는 상근이가 훔쳐야하는 문서이다.
- 알파벳 대문자는 문을 나타낸다.
- 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.
상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.
출력
각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
문제 풀이
다음은 "열쇠" 문제의 정답 코드에 대한 자세한 분석과 풀이 방법입니다.
문제 분석
이 문제는 상근이가 1층 빌딩에 침입하여 최대한 많은 문서를 훔치는 것을 목표로 합니다.
- 맵 구성: 빌딩은
h x w크기의 격자 형태로 주어집니다..: 빈 공간 (이동 가능)*: 벽 (이동 불가능)$: 문서 (획득하면 빈 공간으로 바뀜)A~Z: 문 (해당하는 소문자 열쇠가 있어야 통과 가능)a~z: 열쇠 (획득하면 해당 대문자 문을 열 수 있음)
- 이동: 상하좌우로만 이동할 수 있습니다.
- 시작 위치: 상근이는 빌딩 밖에 있으며, 빌딩 가장자리의 벽이 아닌 모든 곳을 통해 빌딩 안팎을 자유롭게 드나들 수 있습니다.
- 열쇠: 초기에 일부 열쇠를 가지고 있을 수 있으며, 빌딩 안에서 새로운 열쇠를 얻을 수도 있습니다. 열쇠는 여러 번 사용할 수 있습니다.
- 목표: 훔칠 수 있는 문서의 최대 개수를 구합니다.
접근 방법
이 문제는 미로 찾기 유형과 비슷하지만, 열쇠를 획득하여 이전에 막혔던 경로를 열 수 있다는 점에서 일반적인 BFS/DFS보다 복잡합니다. 특정 상태(가지고 있는 열쇠)에 따라 탐색 가능 영역이 달라지기 때문에, 상태를 고려한 탐색이 필요합니다.
선택한 알고리즘은 너비 우선 탐색(BFS) 입니다. BFS를 사용하는 이유는 다음과 같습니다.
- 최단 경로 탐색: 모든 경로의 이동 비용이 동일하므로, BFS는 최단 경로를 통해 모든 도달 가능한 지점을 탐색합니다. (이 문제에서는 최단 경로 자체보다 "모든 도달 가능한 문서"를 찾는 것이 중요합니다.)
- 동적인 탐색 영역 확장: 이 문제의 핵심은 새로운 열쇠를 얻었을 때 이전에 막혔던 문들이 열리면서 탐색 영역이 확장되는 것입니다. 이를 위해 BFS를 한 번만 실행하되, 열쇠를 얻으면 해당 열쇠로 열 수 있는 모든 문 위치를 현재 BFS 큐에 다시 추가하여 탐색을 재개하는 방식을 사용합니다.
구현 설명
주어진 코드는 다음의 주요 단계로 문제를 해결합니다.
1. 맵 확장 및 초기 설정
- 원래
h x w크기의 맵을(h+2) x (w+2)크기로 확장하여.(빈 공간)으로 이루어진 테두리를 추가합니다. 이는 상근이가 빌딩 외부에서 내부로 진입할 수 있는 모든 가장자리 지점을(0,0)에서 시작하는 BFS로 한 번에 탐색할 수 있도록 편의성을 제공합니다. - 주어진 초기 열쇠들을
keys라는set자료구조에 저장하여 열쇠 유무를 효율적으로 확인할 수 있게 합니다. doors라는defaultdict(list)를 선언하여 아직 열쇠가 없어 통과하지 못하는 문들의 위치를 저장합니다. 키는 문의 종류(예: 'A'), 값은 해당 문들의 좌표 리스트입니다.
2. BFS 탐색 시작 및 진행
BFS()함수를 정의하고,visited2차원 배열을False로 초기화하여 방문 여부를 추적합니다.- 탐색 큐
queue에 시작점(0,0)을 넣고visited[0][0]을True로 설정합니다. answer변수를 0으로 초기화하여 훔친 문서의 개수를 세기 시작합니다.- 큐가 빌 때까지 반복하며 BFS를 진행합니다.
3. 각 셀 탐색 로직
- 큐에서 한 좌표
(x, y)를 꺼내 상하좌우 네 방향으로 인접한 셀(sx, sy)을 탐색합니다. - 벽(
*) 처리: 인접 셀이 맵 범위 내에 있고 벽이 아니며, 아직 방문하지 않은 경우에만 다음 로직을 진행합니다. - 문(
A~Z) 처리:- 만약 문
graph[sx][sy]에 해당하는 열쇠graph[sx][sy].lower()가keys에 없다면, 이 문은 현재 잠겨 있습니다. 문graph[sx][sy]의 위치(sx, sy)를doors딕셔너리에 추가하고, 이 경로는 현재 진행할 수 없으므로continue합니다. - 열쇠가 있다면, 문은 열려 있으므로
visited[sx][sy]를True로 만들고 큐에(sx, sy)를 추가합니다.
- 만약 문
- 문서(
$) 처리:answer를 1 증가시키고, 이 문서를 다시 세지 않도록graph[sx][sy]를.으로 바꿉니다.visited[sx][sy]를True로 만들고 큐에(sx, sy)를 추가합니다.
- 열쇠(
a~z) 처리:- 만약
graph[sx][sy]가 아직keys에 없는 새로운 열쇠라면:keys.add(graph[sx][sy])를 통해 이 열쇠를 획득합니다.- 핵심: 이 열쇠
graph[sx][sy]에 해당하는 문graph[sx][sy].upper()이doors딕셔너리에 저장되어 있다면 (즉, 이전에 이 열쇠가 없어 막혔던 문들이 있다면):doors[graph[sx][sy].upper()]에 저장된 모든 문 위치(dx, dy)들을 현재 BFS 큐에 다시 추가합니다. 이는 새로 얻은 열쇠로 인해 이전에 막혔던 문들이 열렸으므로, 그 문들로부터 다시 탐색을 시작해야 함을 의미합니다.- 해당하는 문들의 리스트는 이제 필요 없으므로
del doors[graph[sx][sy].upper()]로 삭제합니다.
visited[sx][sy]를True로 만들고 큐에(sx, sy)를 추가합니다.
- 만약
- 빈 공간(
.) 처리:visited[sx][sy]를True로 만들고 큐에(sx, sy)를 추가합니다.
4. 결과 반환
- 모든 탐색이 끝난 후,
BFS()함수는 총 획득한 문서의 개수answer를 반환하고, 이를 출력합니다.
⏱복잡도 분석
-
시간 복잡도:
O(T * (H * W + K))T: 테스트 케이스의 수.H,W: 맵의 높이와 너비.(H+2) * (W+2)를 편의상N으로 표현하겠습니다.- BFS 탐색의 기본 시간 복잡도는
O(V + E)이며, 여기서V는 정점(셀)의 수N,E는 간선(인접 셀)의 수로4N에 해당합니다. 따라서O(N)입니다. - 이 문제에서는 열쇠 획득 시
doors딕셔너리에 저장된 문 위치들을 큐에 다시 추가하는 과정이 있습니다. 각 셀은visited배열 덕분에 BFS 큐에서 한 번만pop되어 처리됩니다. 즉, 어떤 셀이 잠긴 문이어서doors에 추가되더라도, 열쇠 획득 후 큐에 다시 추가되어 처리될 때visited가True로 바뀌면 다시는 처리되지 않습니다. keysset에 열쇠를 추가하고 확인하는 것은 평균O(1)입니다.doors딕셔너리에 접근하고 리스트를 순회하여 큐에 추가하는 작업은, 최악의 경우 한 종류의 문이 모든 셀을 차지하고, 그 문이 열리는 순간 모든 셀을 큐에 추가해야 할 수 있습니다. 하지만 각 셀은 큐에 추가되어 처리되는 총 횟수가 상수(최대 2번: 첫 탐색에서visited가False인 채로 문에 도달, 열쇠 획득 후doors에서 큐에 추가되어visited가True로 바뀌는 순간)로 제한됩니다.- 따라서 전체적으로
N개의 셀에 대해 각각 상수 시간의 연산을 수행하므로, 하나의 테스트 케이스당 시간 복잡도는O(H * W)에 해당합니다. - 최대
H, W = 100이므로N = 100*100 = 10^4.T=100이므로 총100 * 10^4 = 10^6연산 정도로 충분히 시간 안에 수행됩니다.
-
공간 복잡도:
O(H * W)graph: 확장된 맵 저장을 위해O((H+2)*(W+2))공간이 필요합니다.visited: 방문 여부 저장을 위해O((H+2)*(W+2))공간이 필요합니다.queue: BFS 큐에 최악의 경우 모든 셀이 저장될 수 있으므로O((H+2)*(W+2))공간이 필요합니다.keys: 최대 26개의 열쇠만 저장되므로O(26)입니다.doors:defaultdict에 저장되는 문들의 위치 리스트는 최악의 경우 모든 셀이 문이고 각 문마다 한 번씩 저장될 수 있으므로O((H+2)*(W+2))공간이 필요합니다.- 따라서 지배적인 항은 맵 크기에 비례하는
O(H * W)입니다.
핵심 포인트
-
맵 확장 (Padding): 빌딩 외부에서 내부로 진입하는 모든 경우의 수를 처리하기 위해, 원래 맵의 주위에 한 칸의
.(빈 공간) 테두리를 추가합니다. 이를 통해 BFS의 시작점을(0,0)으로 고정하고 실제 맵의 모든 가장자리 셀을 자연스럽게 탐색할 수 있습니다. -
동적 BFS 및
doors딕셔너리 활용: 새로운 열쇠를 획득했을 때, 이전에 해당 열쇠가 없어 지나가지 못했던 모든 문들을doors딕셔너리에 저장해 두었다가, 열쇠 획득 즉시 이 문들의 위치를 현재 BFS 큐에 추가하여 탐색을 재개합니다. 이는 BFS를 여러 번 재시작하는 것보다 효율적으로 새로운 경로를 탐색할 수 있게 합니다. -
visited배열의 올바른 사용:visited배열은 현재 BFS 탐색에서 이미 방문하여 처리한 셀을 추적하는 데 사용됩니다. 문을 만나서doors딕셔너리에 저장할 때는 해당 문 셀을visited로 표시하지 않습니다. 열쇠를 얻어 해당 문이 큐에 추가되고 실제로pop되어 처리될 때 비로소visited로 표시하여, 한 셀이 두 번 이상 중복 처리되지 않도록 합니다.
풀이 코드
import sys
from collections import deque, defaultdict
input = sys.stdin.readline
t = int(input())
directions = [(1,0),(-1,0),(0,1),(0,-1)]
for _ in range(t):
n, m = map(int, input().split())
graph_input = [list(input().strip()) for _ in range(n)]
key_input = input().strip()
keys = set() if key_input == '0' else set(key_input)
graph = [['.'] * (m+2)]
for row in graph_input:
graph.append(['.'] + row + ['.'])
graph.append(['.'] * (m+2))
n += 2
m += 2
doors = defaultdict(list)
def BFS():
visited = [[False]*m for _ in range(n)]
queue = deque([(0,0)])
visited[0][0] = True
answer = 0
while queue:
x, y = queue.popleft()
for dx, dy in directions:
sx, sy = x + dx, y + dy
if 0<= sx < n and 0<= sy < m and not visited[sx][sy]:
if graph[sx][sy] == '*':
continue
if 'A' <= graph[sx][sy] <= 'Z':
if graph[sx][sy].lower() not in keys:
doors[graph[sx][sy]].append((sx, sy))
continue
visited[sx][sy] = True
if graph[sx][sy] == '$':
answer += 1
graph[sx][sy] = '.'
elif 'a' <= graph[sx][sy] <= 'z':
if graph[sx][sy] not in keys:
keys.add(graph[sx][sy])
if graph[sx][sy].upper() in doors:
for dx, dy in doors[graph[sx][sy].upper()]:
queue.append((dx, dy))
del doors[graph[sx][sy].upper()]
queue.append((sx, sy))
return answer
print(BFS())