フラッドフィル（Flood Fill）アルゴリズムとは？仕組みとC++実装例を解説

フラッドフィル（Flood Fill）アルゴリズムとは

フラッドフィルは、お絵かきソフトの「塗りつぶし（バケツ）ツール」などでも使われている、領域塗りつぶしのための基本的なアルゴリズムです。ここでは、1つの行列（マトリクス）が1枚の画面（スクリーン）を表すものとします。画面上の各要素 (i, j) は1つのピクセルに対応し、そのピクセルの色は異なる数値で表現されます。

このアルゴリズムでは、対象ピクセルが「指定した元の色（前色）」で塗られている場合にのみ、新しい色へと塗り替えます。前色と異なる色のピクセルはそのまま残されます。そして、1つのピクセルを塗り終えるごとに、その上下左右の4方向の隣接ピクセルに対して同じ処理を再帰的に適用していきます。

発想はとてもシンプルです。まず、指定された座標のピクセルが前色で塗られているかどうかを確認します。前色でなければ、そこで処理を終了します。前色であれば、そのピクセルを新しい色で塗り、4つの隣接ピクセルそれぞれに対して同じ手順を再帰的に呼び出します。

入力と出力

入力：
スクリーン行列：
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 2 2 2 2 0 1 0
1 1 1 2 2 0 1 0
1 1 1 2 2 2 2 0
1 1 1 1 1 2 1 1
1 1 1 1 1 2 2 1

出力：
フラッドフィル後のスクリーン行列
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 3 3 3 3 0 1 0
1 1 1 3 3 0 1 0
1 1 1 3 3 3 3 0
1 1 1 1 1 3 1 1
1 1 1 1 1 3 3 1

アルゴリズム

fillScreen(x, y, prevColor, newColor)

入力： 開始座標 (x, y)、前色（prevColor）、新色（newColor）。

出力： 可能であれば、前色を新色に置き換えた後のスクリーン。

Begin
   if (x, y) が画面の範囲外である場合
      return
   if (x, y) の色 ≠ prevColor の場合
      return
   screen[x, y] := newColor
   fillScreen(x+1, y, prevColor, newColor)  // 隣接ピクセル（下）
   fillScreen(x-1, y, prevColor, newColor)  // 隣接ピクセル（上）
   fillScreen(x, y+1, prevColor, newColor)  // 隣接ピクセル（右）
   fillScreen(x, y-1, prevColor, newColor)  // 隣接ピクセル（左）
End

C++による実装例

#include<iostream>
#define M 8
#define N 8
using namespace std;

int screen[M][N] = {    // 画面のサイズと各ピクセルの色
   {1, 1, 1, 1, 1, 1, 1, 1},
   {1, 1, 1, 1, 1, 1, 0, 0},
   {1, 0, 0, 1, 1, 0, 1, 1},
   {1, 2, 2, 2, 2, 0, 1, 0},
   {1, 1, 1, 2, 2, 0, 1, 0},
   {1, 1, 1, 2, 2, 2, 2, 0},
   {1, 1, 1, 1, 1, 2, 1, 1},
   {1, 1, 1, 1, 1, 2, 2, 1}
};

void fillScreen(int x, int y, int prevColor, int newColor) {    // (x, y) の前色を新色に置き換える
   if (x < 0 || x >= M || y < 0 || y >= N)    // 座標が画面の範囲外の場合
      return;

   if (screen[x][y] != prevColor) // ピクセル (x, y) の色が前色と異なる場合は何もしない
      return;

   screen[x][y] = newColor;    // 色を更新
   fillScreen(x+1, y, prevColor, newColor);    // 隣接ピクセル（下）
   fillScreen(x-1, y, prevColor, newColor);    // 隣接ピクセル（上）
   fillScreen(x, y+1, prevColor, newColor);    // 隣接ピクセル（右）
   fillScreen(x, y-1, prevColor, newColor);    // 隣接ピクセル（左）
}

void floodFill(int x, int y, int newColor) {
   int prevColor = screen[x][y];    // 塗り替え前の色を取得
   fillScreen(x, y, prevColor, newColor);
}

int main() {
   int x = 4, y = 4, newColor = 3;
   cout << "塗りつぶし前のスクリーン:" << endl;
   for (int i=0; i<M; i++) {
      for (int j=0; j<N; j++)
         cout << screen[i][j] << " ";
      cout << endl;
   }
   cout << endl;
   floodFill(x, y, newColor);    // (4, 4) を起点に、新色 3 で塗りつぶし

   cout << "塗りつぶし後のスクリーン:" << endl;
   for (int i=0; i<M; i++) {
      for (int j=0; j<N; j++)
         cout << screen[i][j] << " ";
      cout << endl;
   }
}

実行結果

塗りつぶし前のスクリーン:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 2 2 2 2 0 1 0
1 1 1 2 2 0 1 0
1 1 1 2 2 2 2 0
1 1 1 1 1 2 1 1
1 1 1 1 1 2 2 1

塗りつぶし後のスクリーン:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0
1 0 0 1 1 0 1 1
1 3 3 3 3 0 1 0
1 1 1 3 3 0 1 0
1 1 1 3 3 3 3 0
1 1 1 1 1 3 1 1
1 1 1 1 1 3 3 1

計算量と補足

各ピクセルは最大でも1回しか訪問されないため、時間計算量は O(M×N) となります。空間計算量についても、再帰呼び出しの深さ分のメモリが必要となるため、最悪時は O(M×N) です。

なお、大きな画像に対して再帰版をそのまま使用すると、スタックオーバーフローを引き起こす恐れがあります。そのようなケースでは、明示的なキュー（幅優先探索・BFS）やスタック（深さ優先探索・DFS）を用いた反復実装に置き換えると安全です。

フラッドフィルは、ペイント系アプリのバケツツールをはじめ、画像処理、迷路の探索、ゲーム内の同一領域の判定など、幅広い分野で応用されている古典的かつ重要なアルゴリズムです。