Programmers 1844 · 문제 원문 ↗
BFS · Queue · Shortest path
프로그래머스 「게임 맵 최단거리」에서는 1인 칸만 상하좌우로 이동하며 왼쪽 위에서 오른쪽 아래까지 갑니다. 답은 이동 횟수가 아니라 시작과 도착을 포함한 칸 수입니다. 도달할 수 없으면 -1을 반환합니다.
아래는 원문과 별도로 만든 작은 지도입니다. 도착 가능한 지도를 끝까지 재생한 뒤, 칸을 눌러 길을 막아 보세요. 방문한 칸의 숫자는 시작점부터의 최단거리입니다.
현재 상태
풀이의 핵심
- 시작 칸의 거리를 1로 두고 큐에 넣습니다. 나머지는 -1로 둡니다.
- 큐의 앞에서 칸을 꺼냅니다. 이동 가능한 미방문 이웃의 거리를 현재 거리 + 1로 확정합니다.
- 거리를 기록한 이웃을 큐 뒤에 넣습니다. 도착점을 꺼냈다면 그 거리가 답입니다.
- 큐가 빌 때까지 도착하지 못했다면 -1입니다.
모든 이동 비용이 같으므로 BFS는 거리 1, 2, 3… 순서대로 칸을 발견합니다. 거리 d인 칸을 처리하기 전에 더 짧은 거리가 모두 처리되어, 처음 기록한 거리가 최단입니다. DFS에서 처음 찾은 경로에는 이런 보장이 없습니다.
자체 예제의 정답은 9칸입니다. 도착점까지 8번 이동하지만 시작 칸도 세므로 9입니다. 초록색은 부모 정보를 거슬러 복원한 최단 경로 하나입니다.
복잡도와 주의점
R × C 지도에서 각 칸은 큐에 한 번 들어갑니다. 시간과 추가 공간은 모두 O(RC)입니다. Python에서는 deque.popleft()로 큐 앞을 꺼내고, list.pop(0)의 반복적인 원소 이동을 피합니다.
행과 열 길이는 다를 수 있습니다. 거리 배열을 따로 두면 입력 지도를 바꾸지 않아도 됩니다. 이동 비용이 서로 다르면 이 BFS를 그대로 사용할 수 없습니다. 실험의 재생 기록은 제출 코드의 공간 복잡도에 포함되지 않습니다.
직접 작성한 풀이 코드
Python 3
from collections import deque
def solution(maps):
rows, cols = len(maps), len(maps[0])
if maps[0][0] == 0 or maps[-1][-1] == 0:
return -1
distance = [[-1] * cols for _ in range(rows)]
distance[0][0] = 1
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
if r == rows - 1 and c == cols - 1:
return distance[r][c]
for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and maps[nr][nc] == 1 and distance[nr][nc] == -1):
distance[nr][nc] = distance[r][c] + 1
queue.append((nr, nc))
return -1