https://www.acmicpc.net/problem/1194
코드
from collections import deque
n, m = map(int, input().split())
maze = []
start = []
for i in range(n):
line = list(input())
for j in range(m):
if line[j] == "0":
start = [i, j]
line[j] = "."
maze.append(line)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
q = deque([[*start, 0, frozenset()]])
visited = set()
while q:
x, y, d, keys = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
new_keys = keys
can_move = False
if maze[nx][ny] == ".": # 빈 칸
can_move = True
elif maze[nx][ny].isalpha() and maze[nx][ny].islower(): # 열쇠 획득
new_keys = keys | {maze[nx][ny]}
can_move = True
elif maze[nx][ny].isalpha() and maze[nx][ny].isupper() and maze[nx][ny].lower() in keys: # 문 열고 이동
can_move = True
elif maze[nx][ny] == "1":
print(d+1)
exit()
if can_move and (nx, ny, new_keys) not in visited:
q.append([nx, ny, d+1, new_keys])
visited.add((nx, ny, new_keys))
print(-1)
모든 이동이 갖는 가중치가 같았기에 BFS를 사용해야 하는 문제였다. 다만, 주의해야 할 점은 일반적인 BFS와 다르게, 한 번 방문한 점이라도 키를 이전보다 더 갖고 오는 경우에는 다시 방문이 가능해야 한다는 점이다.
예를 들어, 1번째 테스트 케이스에서도 출발점에서 (0, 0)으로 가서 "f" 열쇠를 갖고 다시 출발점을 지나서 "F"문을 열고 지나가야 한다. 이런 경우들이 있을 수 있기 때문에 방문 처리를 할 때, 단순히 그 칸에 이전에 방문했는지 여부만 저장하면 안된다.
나는 방문 처리를 할 때, 칸 위치 정보와 더불어 가진 열쇠의 상태도 처리하도록 구현했다. 민식이가 소유한 열쇠 뭉치는 집합으로 표현했다. 이 때, 중간에 keys는 수정할 수 없는 집합인 `frozenset`에 넣어서 중간에 처리하며 값이 왜곡되는 것을 막았다.
사실 민식이가 소유한 열쇠들을 집합이 아닌 비트마스킹을 이용해서 나타낼 수도 있다. "a"는 0번째 자리수, "b"는 1번째 자리수 이런식으로 말이다. 근데 이렇게 하려면 알파벳을 ASCII 코드로 변경해서 값을 계산하는 과정이 추가되어야 한다.
'문제풀이 > DFS_BFS' 카테고리의 다른 글
| [Javascript/자바스크립트] (프로그래머스) 후보키 (1) | 2025.06.06 |
|---|---|
| [Python/파이썬] 백준 17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 (0) | 2025.05.31 |
| [Javascript/자바스크립트] (프로그래머스) 미로 탈출 (1) | 2025.05.26 |
| [Javascript/자바스크립트] (프로그래머스) 부대복귀 (1) | 2025.05.14 |
| [Javascript/자바스크립트] (프로그래머스) 여행경로 (0) | 2025.05.11 |