파이썬(Python)의 collections.deque를 활용한 가장 표준적인 BFS(너비 우선 탐색) 템플릿입니다. 이 구조를 익혀두시면 '게임 맵 최단거리'뿐만 아니라 대부분의 미로 찾기 문제를 풀 수 있습니다.
1. BFS 기본 코드 템플릿 (Python)
Python
from collections import deque # 효율적인 Queue 구현을 위해 deque 라이브러리를 가져옵니다.
def bfs(maps):
n = len(maps) # 맵의 세로(행, Row) 길이를 구합니다.
m = len(maps[0]) # 맵의 가로(열, Column) 길이를 구합니다.
# 1. 상하좌우 이동을 위한 방향 설정 (x는 행 이동, y는 열 이동)
# dx[0], dy[0]은 위(-1, 0), dx[1], dy[1]은 아래(+1, 0) 식의 쌍입니다.
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 2. 탐색을 시작할 칸(0, 0)을 큐에 넣습니다.
queue = deque([(0, 0)])
# 큐가 빌 때까지(더 이상 갈 수 있는 곳이 없을 때까지) 반복합니다.
while queue:
# 현재 방문한 칸의 좌표를 큐에서 꺼냅니다.
x, y = queue.popleft()
# 현재 위치에서 4방향(상, 하, 좌, 우)을 하나씩 확인합니다.
for i in range(4):
nx = x + dx[i] # 다음 이동할 후보 행 좌표
ny = y + dy[i] # 다음 이동할 후보 열 좌표
# 4. 후보 좌표가 맵의 전체 범위(0 ~ n-1, 0 ~ m-1) 안에 있는지 먼저 체크합니다.
if 0 <= nx < n and 0 <= ny < m:
# 5. 해당 칸이 길(1)인지 확인합니다.
# (이미 방문한 칸은 2 이상의 값을 가지게 되므로 자연스럽게 중복 방문이 방지됩니다.)
if maps[nx][ny] == 1:
# 현재 칸의 거리값에 1을 더해 다음 칸에 저장합니다. (이게 이동 횟수가 됩니다.)
maps[nx][ny] = maps[x][y] + 1
# 다음 탐색을 위해 큐에 새 좌표를 추가합니다.
queue.append((nx, ny))
# 6. 모든 탐색이 끝난 후, 목표 지점(우측 하단 끝)의 값을 가져옵니다.
answer = maps[n-1][m-1]
# 목표 지점의 값이 여전히 1이라면 도달하지 못했다는 뜻이므로 -1을 반환,
# 도달했다면 그 칸에 저장된 최단 거리를 반환합니다.
return answer if answer > 1 else -12. 템플릿의 핵심 포인트
- deque 사용: 일반 리스트의 pop(0)은 $O(N)$의 시간이 걸리지만, deque의 popleft()는 $O(1)$이라서 훨씬 빠릅니다.
- 거리 갱신: maps[nx][ny] = maps[x][y] + 1 부분은 단순히 "방문했다"는 표시를 넘어, 시작점으로부터 몇 칸째인지를 누적해서 기록하는 역할을 합니다.
- 시작점 예외: 이 문제에서는 시작점의 값이 이미 1로 되어 있으므로, 도착지의 값이 여전히 1이라면 한 번도 도달하지 못했다는 뜻이 됩니다. (단, 맵의 크기가 1x1인 경우는 드무니 문제 조건을 확인하세요.)
3. 적용 시 주의사항
- 좌표 체계: 문제에서 (n, m)이 가로/세로 중 어느 쪽인지 헷갈릴 수 있습니다. maps[행][열] 구조이므로 보통 maps[y][x] 또는 maps[row][col] 형태로 접근하는 습관을 들이는 것이 좋습니다.
- 중복 방문 방지: if maps[nx][ny] == 1 조건문이 방문 여부 확인 역할을 수행합니다. 한 번 거리가 갱신된 칸은 1보다 큰 값을 가지게 되어 다시 큐에 들어가지 않습니다.