【Python】行列内のスタートセルからゴールセルまでの最小移動回数をBFSで求める方法

問題概要

N×N の行列 M があり、各セルには「1」「0」「2」「3」のいずれかの値が格納されています。この行列の中で、スタート地点（ソースセル）からゴール地点（デスティネーションセル）まで移動する際に必要となる最小移動回数を求めます。移動は空白セルのみを経由して行うことができ、上下左右の4方向に1マスずつ進むことができます。

• 1 … スタート地点（ソース）のセル
• 2 … ゴール地点（デスティネーション）のセル
• 3 … 移動可能な空白セル
• 0 … 壁（通過不可）

スタートとゴールはそれぞれ必ず1つだけ存在し、スタートからゴールへの経路は複数存在する場合があります。行列上での1回の移動を「1」としてカウントします。

具体例

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

この場合の出力は 5 です。

緑色で示した経路がスタートからゴールまでの最短経路であり、ちょうど5回の移動で到達できます。

解法のアプローチ

この問題は、行列をグラフに変換し、幅優先探索（BFS）によって最短経路を求めることで解けます。手順は以下のとおりです。

1. ノード数 nodes を order × order + 2 として設定します。
2. nodes 個の頂点を持つ空のグラフ g を作成します。
3. k = 1 で初期化します。
4. すべてのセル (i, j) について次を処理します。
   • mat[i][j] != 0 の場合：
     • 右隣 (i, j+1) が有効なら、ノード k と k+1 を結ぶ辺を追加
     • 左隣 (i, j−1) が有効なら、ノード k と k−1 を結ぶ辺を追加
     • 下隣 (i+1, j) が有効なら、ノード k と k+order を結ぶ辺を追加
     • 上隣 (i−1, j) が有効なら、ノード k と k−order を結ぶ辺を追加
   • mat[i][j] == 1 なら src = k を記録
   • mat[i][j] == 2 なら dest = k を記録
   • k += 1
5. src から dest へ BFS を実行し、その結果（最小移動回数）を返します。

実装例

理解を深めるために、次のPythonコードを見てみましょう。

from collections import deque

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj = [[] for _ in range(nodes)]

    def insert_edge(self, src, dest):
        self.adj[src].append(dest)
        self.adj[dest].append(src)

    def BFS(self, src, dest):
        if src == dest:
            return 0
        level = [-1] * self.nodes
        queue = deque([src])
        level[src] = 0
        while queue:
            u = queue.popleft()
            for v in self.adj[u]:
                if level[v] == -1:
                    level[v] = level[u] + 1
                    queue.append(v)
        return level[dest]

def is_ok(i, j, mat):
    global order
    if (i < 0 or i >= order) or (j < 0 or j >= order) or mat[i][j] == 0:
        return False
    return True

def get_min_path(mat):
    global order
    src, dest = None, None
    nodes = order * order + 2
    g = Graph(nodes)
    k = 1
    for i in range(order):
        for j in range(order):
            if mat[i][j] != 0:
                if is_ok(i, j + 1, mat):
                    g.insert_edge(k, k + 1)
                if is_ok(i, j - 1, mat):
                    g.insert_edge(k, k - 1)
                if j < order - 1 and is_ok(i + 1, j, mat):
                    g.insert_edge(k, k + order)
                if i > 0 and is_ok(i - 1, j, mat):
                    g.insert_edge(k, k - order)
            if mat[i][j] == 1:
                src = k
            if mat[i][j] == 2:
                dest = k
            k += 1
    return g.BFS(src, dest)

order = 4
mat = [[3, 3, 1, 0], [3, 0, 3, 3], [3, 3, 0, 3], [0, 3, 2, 3]]
print(get_min_path(mat))

入力

[[3, 3, 1, 0], [3, 0, 3, 3], [3, 3, 0, 3], [0, 3, 2, 3]]

出力

5

まとめ

この手法では、行列の各セルをグラフの頂点とみなし、移動可能な隣接セル同士を辺でつなぐことで迷路のような問題をグラフ探索問題に変換しています。BFSは同一レベルのノードを順に訪問するため、最初にゴールへ到達した時点の距離が自動的に最短移動回数となります。時間計算量・空間計算量はいずれも O(N²) であり、N×N 行列全体に対して効率的に動作します。