Programmers 1844 · 問題文 ↗
BFS · Queue · Shortest path
Programmers「게임 맵 최단거리」では、1のマスを上下左右に移動し、左上から右下へ進みます。求めるのは移動回数ではなく、始点と終点を含むマスの数です。到達できない場合は-1を返します。
実験にはこの解説用に作成した小さなマップを使っています。最後まで再生してからマスを押し、道を塞いでみてください。発見済みのマスの数字は始点からの最短距離です。
現在の状態
解法の考え方
- 始点の距離を1にしてキューに入れます。他の距離は-1にします。
- キューの先頭からマスを取り出します。通行可能で未発見の隣接マスの距離を、現在の距離 + 1に確定します。
- それらをキューの末尾に入れます。ゴールを取り出したら、その距離が答えです。
- 到達前にキューが空になったら-1を返します。
すべての移動コストが等しいため、BFSは距離1、2、3…の順に発見します。距離dのマスを処理する前に、それより短い距離のマスは処理済みなので、最初に記録した距離が最短です。DFSで最初に見つかる経路にはこの保証がありません。
独自の例の答えは9マスです。移動は8回ですが、始点も数えます。緑色は親の情報をたどって復元した最短経路の1つです。
計算量と注意点
R × Cのマップで各マスがキューに入るのは1回です。時間と追加空間はどちらも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