Pythonで迷路行列の脱出に必要な最小移動回数を求める方法

問題の概要

0 を空きセル、1 を壁とする2値行列を考えます。左上のセル (0, 0) から出発し、右下のセル (R-1, C-1) に到達するまでに通過する必要のあるセル数の最小値を求めます。ここで R は行数、C は列数です。ゴールまでの経路が存在しない場合は -1 を返します。

たとえば、次のような入力が与えられたとします。

この場合の出力は 8 になります。以下の表で緑色に示したパスを選ぶことで、合計8個のセルを通って右下のゴールに到達できるためです。

解法のアプローチ：幅優先探索（BFS）

この問題は幅優先探索（BFS）を使うことで効率的に解けます。BFS は始点から近いセルから順に探索を広げていく手法のため、ゴールに最初に到達した時点の距離が必ず最短距離になります。移動は上下左右の4方向に限定され、一度訪れたセルは壁としてマークすることで再訪問を防ぎます。

アルゴリズムの手順

• R := 行数、C := 列数とする
• q := 空のキューを用意し、matrix[0][0] が 0 であれば (0, 0, 1) を挿入する
• matrix[0][0] := 1 として、始点を訪問済みにする
• キュー q から取り出した各要素 (r, c, d) について以下を繰り返す
  • (r, c) が (R-1, C-1) と一致したら、d を返す
  • 隣接セル [(r+1, c), (r-1, c), (r, c+1), (r, c-1)] のそれぞれ (x, y) について
    • 0 <= x < R かつ 0 <= y < C かつ matrix[x][y] == 0 であれば
      • matrix[x][y] := 1 として訪問済みにする
      • (x, y, d + 1) をキュー q の末尾に追加する
• キューが空になったら -1 を返す

Pythonによる実装例

それでは、実際のコードを見てみましょう。

def solve(matrix):
    R, C = len(matrix), len(matrix[0])
    q = [(0, 0, 1)] if not matrix[0][0] else []
    matrix[0][0] = 1
    for r, c, d in q:
        if (r, c) == (R - 1, C - 1):
            return d
        for x, y in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
            if 0 <= x < R and 0 <= y < C and matrix[x][y] == 0:
                matrix[x][y] = 1
                q.append((x, y, d + 1))
    return -1

matrix = [
   [0, 0, 0, 1, 0],
   [0, 0, 1, 1, 0],
   [0, 0, 0, 1, 1],
   [1, 1, 0, 0, 0]
]
print(solve(matrix))

入力

[
[0, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 0, 0, 0]
]

出力

8

計算量について

各セルは高々1回しか訪問されないため、時間計算量は O(R×C)、訪問管理に元の行列をそのまま利用しているため、追加の空間計算量も O(R×C) となります。迷路やグリッド上の最短経路問題では、BFS が最もシンプルかつ確実な選択肢の一つと言えるでしょう。