Pythonでグリッド上の最短経路を探索する：BFSによる最短移動回数の求め方

はじめに

本記事では、記号が書かれたグリッド（マス目）の中で、現在位置からゴールまでの最短移動回数を求めるPythonプログラムを紹介します。この種の迷路・経路探索問題は、幅優先探索（BFS）を用いることで効率的に解くことができます。

グリッドの記号の意味

グリッドには以下の4種類の記号が含まれ、それぞれ次のような意味を持ちます。

• # … ゴールとなるセル。ここへの到達を目指します。
• O … 自由に通行できる空きセル。
• * … 自分の現在位置。
• X … 障害物のあるセル。通過することはできません。

問題の概要

与えられたグリッド上で、現在位置「*」からゴール「#」まで到達するために必要な最小の移動回数を求めます。移動は上下左右の4方向に1マスずつ行えるものとし、ゴールに到達できない場合は -1 を返します。

例として、次のような入力を考えてみましょう。

この場合、現在位置から下へ2マス進めばゴールに届くため、出力は 2 となります。

解き方のアルゴリズム（幅優先探索）

最短距離を求める問題では、BFS（幅優先探索）が有効です。手順は以下の通りです。

1. グリッドの行数を m、列数を n とします。
2. グリッド全体を走査し、「*」の位置 (i, j) を特定します。
3. 答えをカウントする変数 ans を 0 で初期化し、キューに (i, j) を追加します。また、訪問済みを示すため、そのセルを「X」に書き換えます。
4. キューが空になるまで、以下を繰り返します。
   • ans を 1 増やします（1ステップ分の移動を表す）。
   • 新しいキュー newq を用意します。
   • 現在のキュー内の各セルについて、上下左右の隣接セル (ii, jj) を順に調べます。
   • 隣接セルがグリッドの範囲内であり、かつ「X」でない場合は、
     • そのセルが「#」（ゴール）であれば、ans を返して終了します。
     • そうでなければ、(ii, jj) を newq の末尾に追加し、そのセルを「X」に書き換えて再訪問を防ぎます。
   • 処理が終わったら queue を newq で置き換えます。
5. キューが空になってもゴールに到達しなかった場合は、-1 を返します。

既に訪れたセルを「X」に置き換えることで、同じセルを二度以上探索することがなくなり、計算量は O(m × n) に抑えられます。

実装例

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

def solve(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "*": break
        else: continue
        break
    ans = 0
    queue = [(i, j)]
    grid[i][j] = "X"
    while queue:
        ans += 1
        newq = []
        for i, j in queue:
            for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
                if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
                    if grid[ii][jj] == "#": return ans
                    newq.append((ii, jj))
                    grid[ii][jj] = "X"
        queue = newq
    return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

入力

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

出力

2

まとめ

このように、BFSを利用すれば、障害物を避けながらゴールまでの最短移動回数を効率よく求めることができます。ポイントは、探索済みのセルを早めにマークして再訪問を防ぐこと、そして層ごと（ステップごと）にキューを更新することです。迷路探索やゲームAIの経路計算など、さまざまな場面で応用できる基本的なアルゴリズムなので、ぜひ理解しておきましょう。