[PS] BOJ 9328 / 열쇠
![[PS] BOJ 9328 / 열쇠](/content/images/size/w2000/2025/08/-------------4.png)
문제 링크: https://www.acmicpc.net/problem/9328
Thumbnail: Photo by Susan Q Yin (Unsplash)
격자 그래프 상에서 그래프 탐색을 하는 문제입니다!
풀이
BFS
기본적인 풀이는 BFS로, 벽과 길을 구분해 갈 수 있는 곳을 모두 탐색하면 됩니다.
다만, 격자 그래프 상의 타일(각 칸)이 벽과 길만 있는 것이 아니라 문과 열쇠도 함께 배치되어 있어 고려해야 하는 것들이 있습니다.
- 임의의 문을 만났을 때:
- 대응하는 열쇠를 가지고 있다면 -> 그냥 열고 길처럼 지나갈 수 있다.
- 열쇠가 없다면 -> 다른 구간을 탐색해 열쇠를 찾아본다.
- 다른 구간에 열쇠가 있다면 열고 탐색을 이어가야 한다.
- 맵 전체에 열쇠가 없다면 벽으로 취급한다.
문을 열쇠로 최대한 열어가며, 전체 그래프를 탐색해 발견할 수 있는 문서의 총 개수를 구하면 됩니다.
변수 선언
상태 관리를 위해 다양한 변수를 사용했습니다.
DIFF = ((0, 1), (1, 0), (-1, 0), (0, -1)) # BFS에서 다음에 탐색할 노드 정보
queue = deque([])
# 각 케이스 별 격자 그래프의 크기를 전역 변수에 저장하고 사용한다.
H = 0
W = 0
# 미리 2차원 배열을 정의하고, 매 케이스 마다 h x w 크기로 덮어쓰며 사용한다.
visited = [[False for _ in range(100)] for _ in range(100)]
building = [["." for _ in range(100)] for _ in range(100)]
# 각 케이스 별 상태를 기록하는 변수
keys_have = {}
keys_available = {}
entrances = []
restart = False상태 변수들
DIFF: BFS에서, 다음에 탐색할 노드 좌표를 계산하기 위해 사용하는 상수 배열.queue: 모든 BFS에서 공유하는 단일 큐 객체. 매 BFS마다 초기화해서 사용한다.- 다음 두 변수는 매 케이스마다 입력으로 받은 $H$와 $W$의 크기만큼 초기화하며 재사용한다.
visited: 매 케이스마다 각 노드의 방문 여부를 기록할 2차원 배열.building: 매 케이스마다 입력으로 주어진 빌딩의 평면도.
- 다음의 변수들은 각 케이스마다 탐색에 필요한 상태를 저장해두는 변수들이다.
keys_have: 현재 가지고 있는 열쇠를 저장한 Map. 탐색 전에 미리 가지고 있던 열쇠들을 기본 값으로 가지며, 이후 BFS를 통해 열쇠를 발견할 때 마다 여기에 추가한다.entrances: BFS 탐색을 시작할 출입구 좌표를 기록하는 배열입니다. 기본적으로는, 평면도의 테두리 중 진입 가능한 길을 기록합니다.restart: 열쇠를 얻은 뒤 이전에 탐색한 경로를 재탐색하기 위해 사용하는 변수입니다.
입력 처리
- 먼저 $H$와 $W$를 입력 받습니다.
- 그 다음, 평면도를 처리하기 전에 먼저 입력 받아 저장합니다.
- 탐색 전에 가지고 있던 열쇠를 입력 받아
keys_have에 저장합니다. - 빌딩의 평면도를 읽어 저장합니다.
building배열을 $H \times W$ 크기만큼 읽어온 평면도로 덮어씁니다.visited배열을 $H \times W$ 크기만큼False로 초기화합니다.- 평면도의 테두리에 위치한 타일에 대해 다음을 수행합니다.
- 만약 타일이 대문자(문) 이라면, 열 수 있는지 아닌지의 여부를 고려하지 않고 모두 출입구로 판단해
entrances배열에 해당 문의 좌표를 추가합니다.
당장 열쇠를 가지고 있지 않더라도, 탐색 중에 대응되는 열쇠를 찾을 수 있기 때문입니다. - 타일이 열쇠라면, 해당 열쇠를
keys_have에 추가하고 출입구로 판단해entrances배열에 해당 좌표를 추가합니다. - 타일이 문서(
$)라면, 문서의 개수(cnt)를 1 증가시키고entrances배열에 해당 좌표를 추가합니다. - 타일이 길(
.)이라면,entrances배열에 해당 좌표를 추가합니다.
- 만약 타일이 대문자(문) 이라면, 열 수 있는지 아닌지의 여부를 고려하지 않고 모두 출입구로 판단해
H, W = map(int, input().split())
cnt = 0
building_str = [input().strip() for _ in range(H)]
# 이미 가지고 있는 열쇠 등록하기
keys = input().strip()
if keys != "0":
keys_have.update({k.upper(): True for k in keys})
# 빌딩 지도 읽어오기
for r in range(H):
for c, tile in enumerate(building_str[r]):
building[r][c] = tile
visited[r][c] = False
if (r == 0 or r == H - 1 or c == 0 or c == W - 1) and tile != "*":
if tile.isupper():
entrances.append((r, c)) # 일단 모든 문은 출입구로 고려해본다.
elif tile.islower():
keys_have[tile.upper()] = True
building[r][c] = "."
entrances.append((r, c))
else:
if tile == "$":
cnt += 1
building[r][c] = "."
entrances.append((r, c))케이스 별 입력 처리
BFS
이제 BFS를 구현해야 합니다.
BFS 함수는 매개변수로 탐색을 시작하는 좌표 $(R, C)$를 받아 해당 노드에서부터 탐색을 시작합니다.
이때, building[R][C]가 진입 가능한지 먼저 판단합니다. 앞서 당장 열 수 없는 문이더라도 출입구로 고려했기 때문입니다.
BFS를 진행하며, 다음에 탐색할 노드의 좌표는 DIFF를 사용해 계산합니다. DIFF는 다음에 탐색할 상하좌우 노드를 계산하기 위한 행/열 좌표의 차이를 저장한 상수 배열입니다.
DIFF를 통해 계산한 다음 탐색 좌표 (nr, nc)에 대해, 다음 조건이 맞다면 탐색을 진행합니다:
- 빌딩의 범위 안에 위치하는가?
- $0 \le nr < H$ && $0 \le nc < W$
(nr, nc)를 이전에 방문하지 않았을 때 (visited배열 사용)
다음 노드의 탐색은 해당 좌표에 위치한 타일의 종류에 따라 진행합니다.
- 만약 해당 타일이 문이라면
- 열쇠를 가지고 있는 경우는 문을 열고 이어서 탐색을 진행합니다.
- 그렇지 않다면, 벽과 동일하게 고려합니다.
- 만약 해당 타일이 열쇠라면
keys_have에 해당 열쇠를 추가합니다.restart전역 변수를True로 바꿉니다. 이를 통해 이전에 탐색했던 출입구를 다시 탐색해줍니다.
- 만약 문서(
$)라면- 문서 개수(
cnt)를 1 증가시킵니다. - 이후는 길과 동일합니다.
- 문서 개수(
- 만약 길(
.)이라면- 해당 좌표를 이어서 탐색합니다.
- 만약 벽(
*)이라면- 더 이상 탐색하지 않습니다.
def bfs(R, C):
# 진입 전 전처리
tile = building[R][C]
if (tile.isupper() and not keys_have.get(tile, False)) or visited[R][C] or tile == "*": # 벽이거나 기존에 방문한 경우 or 열쇠를 가지고 있지 않은 문
return 0
queue.append((R, C))
visited[R][C] = True
cnt = 0
while queue:
r, c = queue.popleft()
for dr, dc in DIFF:
nr = r + dr
nc = c + dc
if 0 <= nr < H and 0 <= nc < W and not visited[nr][nc]:
# 타일 종류에 따라 처리하기
tile = building[nr][nc]
if tile.isalpha():
if tile.isupper() and keys_have.get(tile, False): # 열쇠를 가지고 있는 잠긴 문.
visited[nr][nc] = True
building[nr][nc] = "." # 영구적으로 열어둔다.
queue.append((nr, nc))
elif tile.islower(): # 열쇠
keys_have[tile.upper()] = True # 열쇠 획득
visited[nr][nc] = True
building[nr][nc] = "." # 이미 주운 열쇠는 맵에서 치운다.
global restart
restart = True
return cnt
elif tile != "*":
if tile == "$":
cnt += 1
visited[nr][nc] = True
building[nr][nc] = "." # Prevent counting twice.
queue.append((nr, nc))
return cntBFS
이 BFS를 각각의 출입구(entrances)에 대해 수행합니다. 탐색 도중 열쇠를 발견했다면, 이전 탐색 시 열지 못했던 문을 열 가능성이 있으므로 전체 출입구를 다시 탐색합니다. 이는 전역 변수로 선언한 restart 변수를 통해 조절됩니다.
# BFS
idx = 0
while idx < len(entrances):
r, c = entrances[idx]
cnt += bfs(r, c)
idx += 1
if restart:
for r in range(H):
for c in range(W):
visited[r][c] = False
queue.clear()
idx = 0
restart = False
print(cnt)탐색 이후
여러 개의 테스트 케이스에 대해 같은 동작을 반복해야 하므로, 상태 변수를 매번 선언해서 사용하기보다 전역 변수로 선언한 뒤 재사용하는 방법으로 구현했습니다.
그에 따라, 각 테스트 케이스의 결과 출력 이후 상태 변수들을 초기화해야 합니다.
초기화해야 하는 변수들은 다음과 같습니다.
queuekeys_haveentrances
다음 변수들은 다음 테스트 케이스의 입력을 처리하며 초기화되므로 굳이 하단에서 초기화할 필요는 없습니다.
buildingvisitedH와Wcnt
for _ in range(int(input())):
H, W = map(int, input().split())
cnt = 0
...
# 상태변수 초기화
queue.clear()
keys_have.clear()
entrances.clear()상태 변수 초기화
전체 코드
from collections import deque
input = open(0).readline
DIFF = ((0, 1), (1, 0), (-1, 0), (0, -1))
queue = deque([])
# 각 케이스 별 격자 그래프의 크기를 전역 변수에 저장하고 사용한다.
H = 0
W = 0
# 미리 2차원 배열을 정의하고, 매 케이스 마다 h x w 크기로 덮어쓰며 사용한다.
visited = [[False for _ in range(100)] for _ in range(100)]
building = [["." for _ in range(100)] for _ in range(100)]
# 각 케이스 별 상태를 기록하는 변수
keys_have = {}
entrances = []
restart = False
def bfs(R, C):
# 진입 전 전처리
tile = building[R][C]
if (tile.isupper() and not keys_have.get(tile, False)) or visited[R][C] or tile == "*": # 벽이거나 기존에 방문한 경우 or 열쇠를 가지고 있지 않은 문
return 0
queue.append((R, C))
visited[R][C] = True
cnt = 0
while queue:
r, c = queue.popleft()
for dr, dc in DIFF:
nr = r + dr
nc = c + dc
if 0 <= nr < H and 0 <= nc < W and not visited[nr][nc]:
# 타일 종류에 따라 처리하기
tile = building[nr][nc]
if tile.isalpha():
if tile.isupper() and keys_have.get(tile, False): # 열쇠를 가지고 있는 잠긴 문.
visited[nr][nc] = True
building[nr][nc] = "." # 영구적으로 열어둔다.
queue.append((nr, nc))
elif tile.islower(): # 열쇠
keys_have[tile.upper()] = True # 열쇠 획득
visited[nr][nc] = True
building[nr][nc] = "." # 이미 주운 열쇠는 맵에서 치운다.
global restart
restart = True
return cnt
elif tile != "*":
if tile == "$":
cnt += 1
visited[nr][nc] = True
building[nr][nc] = "." # Prevent counting twice.
queue.append((nr, nc))
return cnt
for _ in range(int(input())):
H, W = map(int, input().split())
cnt = 0
building_str = [input().strip() for _ in range(H)]
# 이미 가지고 있는 열쇠 등록하기
keys = input().strip()
if keys != "0":
keys_have.update({k.upper(): True for k in keys})
# 빌딩 지도 읽어오기
for r in range(H):
for c, tile in enumerate(building_str[r]):
building[r][c] = tile
visited[r][c] = False
if (r == 0 or r == H - 1 or c == 0 or c == W - 1) and tile != "*":
if tile.isupper():
entrances.append((r, c)) # 일단 모든 문은 출입구로 고려해본다.
elif tile.islower():
keys_have[tile.upper()] = True
building[r][c] = "."
entrances.append((r, c))
else:
if tile == "$":
cnt += 1
building[r][c] = "."
entrances.append((r, c))
# BFS
idx = 0
while idx < len(entrances):
r, c = entrances[idx]
cnt += bfs(r, c)
idx += 1
if restart:
for r in range(H):
for c in range(W):
visited[r][c] = False
queue.clear()
idx = 0
restart = False
print(cnt)
# 상태변수 초기화
queue.clear()
keys_have.clear()
entrances.clear()solution.py