Pythonでマトリックスを幅優先探索（BFS）して最短距離を求める方法

マトリックス（2次元配列）上の要素を解析する場合、各セルから確認できるのは「左」「右」「下」「上」の4方向です。

幅優先探索（Breadth First Search／BFS）とは、与えられた2次元マトリックス上の2つの要素間の最短距離を求めるアルゴリズムです。各セルに対しては4つの操作が可能で、それぞれ次の数値で表現されます。

• 「2」 … そのセルがスタート地点（ソース）であることを示す
• 「3」 … そのセルがゴール（デスティネーション）であることを示す
• 「1」 … そのセルからさらに別の方向へ移動できることを示す
• 「0」 … そのセルからはどの方向にも移動できないことを示す

以上の条件に基づいて、与えられたマトリックスに対して幅優先探索を実行することができます。

問題を解くためのアプローチ

マトリックス全体を探索し、セル間の最小距離（最短距離）をBFSで求めるためのアルゴリズムの手順は以下の通りです。

• まず行数と列数を入力として受け取る。
• 指定された行数・列数でマトリックスを初期化する。
• 行・列・マトリックスを引数に受け取り、要素間の最短距離を返す関数 findDistance を用意する。
• スタート（source）とゴール（destination）の位置を記録するための変数を初期化する。
• セルの値が「3」であればゴールとして、「2」であればスタートとしてマークする。
• BFSを実装するためにキューを初期化する。
• セルの行番号と列番号をペアとしてキューに挿入し、取り出しながら隣接セルを調べる。隣のセルへ「現在の距離＋1」で到達できる従来の距離よりも短い場合は距離を更新する。
• 上下左右のすべての方向に対して同様の処理を繰り返し、各セルの最小距離を求めていく。
• 最後にゴールセルの距離を結果として返す。

サンプルコード

import queue
INF = 10000
class Node:
    def __init__(self, i, j):
        self.row_num = i
        self.col_num = j

def findDistance(row, col, mat):
    source_i = 0
    source_j = 0
    destination_i = 0
    destination_j = 0
    # スタート（2）とゴール（3）の座標を探す
    for i in range(0, row):
        for j in range(0, col):
            if mat[i][j] == 2 :
                source_i = i
                source_j = j
            if mat[i][j] == 3 :
                destination_i = i
                destination_j = j
    # 距離テーブルを無限大（INF）で初期化
    dist = []
    for i in range(0, row):
        sublist = []
        for j in range(0, col):
            sublist.append(INF)
        dist.append(sublist)
    # BFSを開始するためのキューを初期化
    q = queue.Queue()
    source = Node(source_i, source_j)
    q.put(source)
    dist[source_i][source_j] = 0

    # 条件チェックを加えた幅優先探索
    while (not q.empty()):
        # キューの先頭からノードを取り出す
        temp = q.get()
        x = temp.row_num
        y = temp.col_num

        # 左へ移動できる場合（移動先が道「1」またはゴール「3」）
        if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3) :
            # 既存の距離より短く到達できる場合は更新
            if dist[x][y] + 1 < dist[x][y - 1] :
                dist[x][y - 1] = dist[x][y] + 1
                next = Node(x, y - 1)
                q.put(next)

        # 右へ移動できる場合
        if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3) :
            if dist[x][y] + 1 < dist[x][y + 1] :
                dist[x][y + 1] = dist[x][y] + 1
                next = Node(x, y + 1)
                q.put(next)

        # 上へ移動できる場合
        if x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3) :
            if dist[x][y] + 1 < dist[x - 1][y] :
                dist[x - 1][y] = dist[x][y] + 1
                next = Node(x - 1, y)
                q.put(next)

        # 下へ移動できる場合
        if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3) :
            if dist[x][y] + 1 < dist[x + 1][y] :
                dist[x + 1][y] = dist[x][y] + 1
                next = Node(x + 1, y)
                q.put(next)
    return dist[destination_i][destination_j]

row = 5
col = 5
mat = [ [1, 0, 0, 2, 1],
        [1, 0, 2, 1, 1],
        [0, 1, 1, 1, 0],
        [3, 2, 0, 0, 1],
        [3, 1, 0, 0, 1] ]

answer = findDistance(row, col, mat);
if answer == INF :
    print("パスが見つかりません")
else:
    print("ソースからデスティネーションまでの最短距離:")
    print(answer)

実行結果

ソースからデスティネーションまでの最短距離:
2

コードのポイント

このサンプルのマトリックスには、値が「2」のスタートセルが複数存在します。BFSはそれらのスタートを起点として探索を広げていき、ゴール（値が「3」のセル）に到達するまでの最小ステップ数を求めます。

今回の例では、3行目のスタート (3, 1) から下のセル (4, 1) を経由してゴール (4, 0) へ進む経路が最短となり、答えは「2」になります。もし移動可能なセル（「1」や「3」）だけをつなぐ経路が一切存在しない場合は、距離が INF のまま残るため、「パスが見つかりません」と表示されます。

計算量

時間計算量は O(row × col)、空間計算量も距離テーブルとキューの分だけ O(row × col) となります。各セルは必要以上に何度も処理されないため、マトリックスのサイズに比例した効率の良い探索が可能です。