Pythonでフラッドフィル（塗りつぶし）アルゴリズムを実装して色を一括置換する方法

2次元グリッドがあり、各セルには文字列 "r"・"g"・"b" のいずれかの色が格納されているとします。このグリッドに対して、行 r・列 c を起点として、指定した色 target でフラッドフィル（flood fill：塗りつぶし）操作を行います。

フラッドフィルとは、開始セル grid[r][c] と同じ色を持ち、上下左右に隣接して連結しているすべてのセルを、目標色 target へ一括置換する操作です。画像編集ソフトの「バケツツール」でおなじみのアルゴリズムですね。

入力例と出力例

たとえば、次のようなグリッドが与えられたとします。

ここで (0, 0) を起点に緑（"g"）で塗りつぶすと、結果は次のようになります。

(0, 0) に連結していた赤（"r"）のセルがすべて緑（"g"）に置き換えられました。一方、連結していないセルは元の色のまま変化しません。

解法のアプローチ：DFS（深さ優先探索）

この問題は、深さ優先探索（DFS）を再帰的に使うことで簡潔に実装できます。手順は以下の通りです。

• 訪問済みセルを記録するための集合 seen を用意する
• oldcolor に開始セル matrix[r][c] の元の色を保存する
• 再帰関数 dfs(i, j) を定義する
• dfs の中では、(i, j) がグリッドの範囲内にあり、未訪問で、かつ色が oldcolor と一致する場合に、次の処理を行う
  • (i, j) を seen に追加する
  • matrix[i][j] を target に更新する
  • 上下左右の4方向に対して再帰的に dfs を呼び出す
• メイン処理から dfs(r, c) を呼び出し、最後に matrix を返す

実装コード

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, matrix, r, c, target):
        def dfs(i, j):
            if (
                i >= 0
                and i < len(matrix)
                and j >= 0
                and j < len(matrix[0])
                and (i, j) not in seen
                and matrix[i][j] == oldcolor
            ):
                seen.add((i, j))
                matrix[i][j] = target
                dfs(i + 1, j)
                dfs(i, j + 1)
                dfs(i, j - 1)
                dfs(i - 1, j)
        seen = set()
        oldcolor = matrix[r][c]
        dfs(r, c)
        return matrix

ob = Solution()
matrix = [ ["r", "r", "r"], ["r", "g", "b"], ["g", "b", "b"] ]
r = 0
c = 0
target = "g"
print(ob.solve(matrix, r, c, target))

入力

matrix = [
["r", "r", "r"],
["r", "g", "b"],
["g", "b", "b"] ]
r = 0
c = 0
target = "g"

出力

[['g', 'g', 'g'], ['g', 'g', 'b'], ['g', 'b', 'b']]

計算量と実装上の注意点

このアルゴリズムの計算量は以下の通りです。

• 時間計算量： O(行数 × 列数)。各セルは最大1回しか訪問されないためです。
• 空間計算量： O(行数 × 列数)。再帰呼び出しのスタックと seen 集合が最悪ケースでグリッド全体分のメモリを消費します。

なお、非常に大きなグリッドを扱う場合は、Pythonの再帰上限（デフォルトで約1000回）に達する可能性があります。その際は sys.setrecursionlimit() で上限を引き上げるか、スタックを使った反復版DFS、あるいはキューを使ったBFS（幅優先探索）への書き換えを検討するとよいでしょう。