Pythonで2Dグリッド内のサイクル(閉路)を検出するプログラム

m × n のサイズを持つ文字からなる2次元配列 grid があるとします。このグリッドの中にサイクル(閉路)が存在するかどうかを判定する必要があります。ここでいうサイクルとは、長さ4以上の経路で、開始位置と終了位置が同じセルになるものを指します。移動は上・下・左・右の4方向に行えますが、移動先のセルは現在のセルと同じ値を持っている必要があり、また一度訪れたセルを再訪することはできません。

たとえば、入力が以下のような場合を考えてみます。

この場合の出力は True になります。緑色のセルはすべて文字「m」で構成されており、外周に沿って一周するループ状の経路(サイクル)を形成しているためです。

解決アプローチ

この問題は、DFS(深さ優先探索)と3色マーキング(WHITE / GRAY / BLACK)を組み合わせることで効率的に解けます。ポイントは、探索中のセル(GRAY)に再び到達したとき、それが直前のセルからの単なる戻りでなければ、サイクルが存在すると判断できるという点です。

アルゴリズムの手順

• WHITE := 0、GRAY := 1、BLACK := 2 と定義します。
• R := グリッドの行数、C := グリッドの列数とします。
• color := デフォルト値が 0(WHITE)の辞書を用意します。
• dfs(r, c, pr = -1, pc = -1) 関数を定義します。pr と pc は直前にいたセル(親セル)の座標です。
• color[r, c] := GRAY と設定します。
• 方向リスト di の各オフセット (x, y) について、次を繰り返します。
  • (nr, nc) := (r + x, c + y) とします。
  • 0 ≤ nr < R かつ 0 ≤ nc < C かつ grid[r][c] == grid[nr][nc] かつ (nr, nc) ≠ (pr, pc) を満たす場合:
    • color[nr, nc] == WHITE であれば、dfs(nr, nc, r, c) が True を返したら True を返します。
    • そうでなく color[nr, nc] == GRAY であれば、True を返します(サイクルを検出)。
• color[r, c] := BLACK と設定し、False を返します。
• メイン処理では、すべてのセル (r, c) について color[r, c] == WHITE であれば dfs(r, c) を呼び出し、True が返れば True を返します。
• 最後に False を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

from collections import defaultdict

di = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def solve(grid):
    WHITE, GRAY, BLACK = 0, 1, 2
    R, C = len(grid), len(grid[0])

    color = defaultdict(int)

    def dfs(r, c, pr=-1, pc=-1):
        color[r, c] = GRAY
        for x, y in di:
            nr, nc = r + x, c + y
            if (0 <= nr < R and 0 <= nc < C
                    and grid[r][c] == grid[nr][nc]
                    and (nr, nc) != (pr, pc)):
                if color[nr, nc] == WHITE:
                    if dfs(nr, nc, r, c):
                        return True
                elif color[nr, nc] == GRAY:
                    return True

        color[r, c] = BLACK
        return False

    for r in range(R):
        for c in range(C):
            if color[r, c] == WHITE:
                if dfs(r, c):
                    return True
    return False

matrix = [["m", "m", "m", "p"],
          ["m", "k", "m", "m"],
          ["m", "m", "s", "m"],
          ["f", "m", "m", "m"]]
print(solve(matrix))

入力

[["m","m","m","p"], ["m","k","m","m"], ["m","m","s","m"], ["f","m","m","m"]]

出力

True

計算量の目安

各セルは最大でも定数回しか訪問されないため、時間計算量は O(R × C) です。color 辞書と再帰呼び出しのスタックが必要となるため、空間計算量も O(R × C) となります。