【Python】マトリックス内の同一値のセルがサイクルを形成するかどうかを判定する方法

2次元のマトリックス(行列)が与えられたとき、あるセルを出発点として選び、上下左右に隣接する同じ値のセルへ移動しながら進み、再び出発点に戻れるかどうか(つまりサイクルが存在するかどうか)を判定します。ただし、直前のステップで訪れたセルにはすぐに戻ることはできません。

たとえば、入力が以下のマトリックスだった場合を考えてみましょう。

この場合、出力は True になります。「2」のセルを順にたどると環状の経路(サイクル)が形成されるためです。

解決のためのアルゴリズム

この問題は、深さ優先探索(DFS)を使うことで効率的に解けます。手順は以下の通りです。

• R := マトリックスの行数
• C := マトリックスの列数
• vis := R × C のサイズのマトリックスを作成し、すべて False で初期化(訪問済みフラグ)
• dfs() 関数を定義する。引数として出発点 root を受け取る
• stack := root と None を要素にもつスタックを用意する
• vis[root[0]][root[1]] := True とする
• スタックが空でない間、以下を繰り返す
  • [v, prev] := スタックの先頭要素を取り出す(pop)
  • v の各近傍 w に対して以下を実行する
    • w が prev と異なる場合:
      • vis[w[0]][w[1]] が False なら、訪問済みにして [w, v] をスタックに push する
      • すでに訪問済みなら、サイクルが見つかったので True を返す
• 最後までサイクルが見つからなければ False を返す

メイン処理では、すべてのセルを走査し、まだ訪問していないセルから dfs() を開始します。どれかひとつの dfs() が True を返せば、その時点でサイクルの存在が確定します。

実装例(Python)

class Solution:
    def solve(self, matrix):
        R = len(matrix)
        C = len(matrix[0])

        def get_neighbors(i, j):
            val = matrix[i][j]
            for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == val:
                    yield ii, jj

        vis = [[False] * C for _ in range(R)]

        def dfs(root):
            stack = [(root, None)]
            vis[root[0]][root[1]] = True
            while stack:
                v, prev = stack.pop()
                for w in get_neighbors(*v):
                    if w != prev:
                        if not vis[w[0]][w[1]]:
                            vis[w[0]][w[1]] = True
                            stack.append((w, v))
                        else:
                            return True
            return False

        for i in range(R):
            for j in range(C):
                if not vis[i][j]:
                    if dfs((i, j)):
                        return True
        return False

ob = Solution()
matrix = [
    [2, 2, 2, 1],
    [2, 1, 2, 1],
    [2, 2, 2, 1]
]
print(ob.solve(matrix))

入力

[
[2, 2, 2, 1],
[2, 1, 2, 1],
[2, 2, 2, 1] ]

出力

True

コードのポイント

この実装では、再帰呼び出しの代わりに明示的なスタックを使った反復型のDFSを採用しています。そのため、大きなマトリックスを扱う際にもPythonの再帰上限(recursion limit)を気にせず安全に処理できます。

また、「直前にいたセル(prev)には戻らない」という条件があることで、単純な往復移動をサイクルと誤認識することを防いでいます。既に訪問済みのセルへ別の経路から到達した場合にのみ、サイクルが存在すると判定される仕組みです。

計算量については、各セルと各隣接関係を高々一度ずつしか処理しないため、O(R × C) となり、非常に効率的です。