메모리: 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를 사용하는 이유는 다음과 같습니다.
주어진 코드는 다음의 주요 단계로 문제를 해결합니다.
h x w 크기의 맵을 (h+2) x (w+2) 크기로 확장하여 . (빈 공간)으로 이루어진 테두리를 추가합니다. 이는 상근이가 빌딩 외부에서 내부로 진입할 수 있는 모든 가장자리 지점을 (0,0)에서 시작하는 BFS로 한 번에 탐색할 수 있도록 편의성을 제공합니다.keys라는 set 자료구조에 저장하여 열쇠 유무를 효율적으로 확인할 수 있게 합니다.doors라는 defaultdict(list)를 선언하여 아직 열쇠가 없어 통과하지 못하는 문들의 위치를 저장합니다. 키는 문의 종류(예: 'A'), 값은 해당 문들의 좌표 리스트입니다.BFS() 함수를 정의하고, visited 2차원 배열을 False로 초기화하여 방문 여부를 추적합니다.queue에 시작점 (0,0)을 넣고 visited[0][0]을 True로 설정합니다.answer 변수를 0으로 초기화하여 훔친 문서의 개수를 세기 시작합니다.(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)를 추가합니다.BFS() 함수는 총 획득한 문서의 개수 answer를 반환하고, 이를 출력합니다.시간 복잡도: O(T * (H * W + K))
T: 테스트 케이스의 수.H, W: 맵의 높이와 너비. (H+2) * (W+2)를 편의상 N으로 표현하겠습니다.O(V + E)이며, 여기서 V는 정점(셀)의 수 N, E는 간선(인접 셀)의 수로 4N에 해당합니다. 따라서 O(N) 입니다.doors 딕셔너리에 저장된 문 위치들을 큐에 다시 추가하는 과정이 있습니다. 각 셀은 visited 배열 덕분에 BFS 큐에서 한 번만 pop되어 처리됩니다. 즉, 어떤 셀이 잠긴 문이어서 doors에 추가되더라도, 열쇠 획득 후 큐에 다시 추가되어 처리될 때 visited가 True로 바뀌면 다시는 처리되지 않습니다.keys set에 열쇠를 추가하고 확인하는 것은 평균 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())