Pythonで2値行列の最大パス長を求めるアルゴリズムを解説

この問題では、各要素が0または1であるm×nの正方行列mat[][]が与えられます。要素が1の場合は「接続されている」ことを、0の場合は「接続されていない」ことを意味します。私たちのタスクは、この2値行列における最大パス長を見つけることです。

問題の説明

この問題を解くには、行列上の最も長いパス、つまり行列内のすべての1の要素をつなぐ経路の最大長を求める必要があります。ただし、パスを求める前に、最大で1つの0を1に変換することが許されています。この変換をうまく行うことで、パス長を最大化できるのがポイントです。

具体例で問題を確認してみましょう。

入力例

mat[][] = {{1, 0},
{0, 1}}

出力例

3

説明

インデックス(0, 1)または(1, 0)の0を1に変換することで、
パス長を最大にできます。

この例では、どちらか一方の0を1に変換すると、対角線上に3つの1が並び、パス長は3になります。

解法アプローチ

単純な解法

最もシンプルな方法は、それぞれの0を1に変換した場合のパス長をすべて計算することです。深さ優先探索（DFS）を使ってパス長を求め、その中で最大のものを返します。しかし、この方法では変換のたびに探索をやり直すため、計算コストが高くなります。

効率的な解法

より効率的なアプローチは、複数回の変換・再計算を避け、最も有望な1つの変換だけに絞ることです。具体的には、次の手順で進めます。

1. DFSを使って、互いに接続された1の集合（連結成分）ごとにグループ化し、それぞれのサイズを記録します。各グループには2以降の一意なインデックスを割り当てます。
2. すべての0のマスについて、上下左右の隣接マスを調べ、隣接する異なるグループのサイズを合計します。
3. 「その0自身を1に変換した場合のパス長（隣接グループの合計＋1）」を計算し、最大値を更新していきます。

こうすることで、実際に0を1に書き換えて再探索する必要がなく、一度の走査で答えを求められます。

ソリューションの実装例

以下は、この解法の動作を示すPythonプログラムです。

def findNeighbors(R, C, N):
    for nr, nc in (((R - 1), C), ((R + 1), C), (R, (C - 1)), (R, (C + 1))):
        if 0 <= nr < N and 0 <= nc < N:
            yield nr, nc

def DFSTraversal(R, C, index, mat, N):
    maxLen = 1
    mat[R][C] = index
    for nr, nc in findNeighbors(R, C, N):
        if mat[nr][nc] == 1:
            maxLen += DFSTraversal(nr, nc, index, mat, N)
    return maxLen

def findLargestPath(mat):

    N = len(mat)
    maxPath = {}
    index = 2

    # 各連結成分をグループ化し、サイズを記録
    for i in range(N):
        for j in range(N):
            if mat[i][j] == 1:
                maxPath[index] = DFSTraversal(i, j, index, mat, N)
                index += 1

    maxPathLen = max(maxPath.values() or [0])

    # 各0のマスについて、隣接グループをつなげた場合の長さを評価
    for i in range(N):
        for j in range(N):
            if mat[i][j] == 0:
                seen = {mat[nr][nc] for nr, nc in findNeighbors(i, j, N) if mat[nr][nc] > 1}
                maxPathLen = max(maxPathLen, 1 + sum(maxPath[g] for g in seen))

    return maxPathLen

I = [[1, 0], [0, 1]]
print("最大パスの長さは " + str(findLargestPath(I)))

出力

最大パスの長さは 3

計算量について

このアルゴリズムでは、行列の全マスを高々数回走査するだけで済みます。連結成分のラベリングにO(N²)、各0のマスの評価にもO(N²)程度しかかからないため、全体の時間計算量はO(N²)、空間計算量もO(N²)となります。0を1に変換して毎回DFSをやり直す単純な手法（O(N⁴)になる可能性）と比べて、大幅に効率化できる点がこの解法の大きな利点です。

まとめ

2値行列の最大パス長を求める問題は、DFSによる連結成分のグループ化と、各0のマスでの隣接グループの結合評価を組み合わせることで効率的に解けます。「最大で1つの0を1に変換できる」という条件を活かし、無駄な再計算を省くことが、高性能な実装への鍵となります。