플러드 필(Flood Fill) 알고리즘: 개념, 동작 원리, C++ 구현 예제

하나의 행렬(matrix)이 주어지며, 이 행렬은 하나의 화면(screen)을 나타냅니다. 화면의 각 요소 (i, j)를 픽셀(pixel)이라고 부르고, 각 픽셀의 색상은 서로 다른 숫자로 표시합니다. 플러드 필 알고리즘에서는 선택된 픽셀이 기존 색상(prevColor)을 가지고 있을 때 그 픽셀을 새로운 색상(newColor)으로 채웁니다. 만약 픽셀의 색상이 기존 색상과 다르다면 해당 픽셀은 채우지 않습니다. 하나의 픽셀을 채운 뒤에는 위, 아래, 왼쪽, 오른쪽에 인접한 픽셀들에 대해 같은 작업을 반복 수행합니다.

핵심 아이디어는 매우 간단합니다. 먼저 선택된 위치가 기존 색상으로 칠해져 있는지 확인하고, 그렇지 않다면 알고리즘을 종료합니다. 기존 색상이라면 해당 픽셀을 새로운 색으로 채운 후, 네 방향의 이웃 픽셀에 대해 재귀적으로 동일한 과정을 수행합니다. 이는 그래프 탐색 기법 중 DFS(깊이 우선 탐색)을 응용한 방식입니다.

입력 및 출력 예시

입력:
화면 행렬:
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

위 예시에서는 좌표 (4, 4)에서 시작하여 값이 2인 영역 전체를 새로운 색상인 3으로 채웁니다. 기존 색상 2로 연결된 픽셀들만 변경되고, 다른 숫자를 가진 픽셀은 그대로 유지되는 것을 확인할 수 있습니다.

알고리즘 의사 코드

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)가 prevColor가 아니면 아무 작업도 하지 않음
        return;

    screen[x][y] = newColor;    // 색상 업데이트
    fillScreen(x+1, y, prevColor, newColor);    // (x, y)의 오른쪽
    fillScreen(x-1, y, prevColor, newColor);    // (x, y)의 왼쪽
    fillScreen(x, y+1, prevColor, newColor);    // (x, y)의 위쪽
    fillScreen(x, y-1, prevColor, newColor);    // (x, y)의 아래쪽
}

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 << "Previous screen: "<< 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 << "Updated screen: "<< endl;
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++)
            cout << screen[i][j] << " ";
        cout << endl;
    }
}

실행 결과

Previous screen
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

Updated screen:
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

복잡도 분석

• 시간 복잡도: O(M × N) — 화면의 모든 픽셀을 최대 한 번씩만 방문하므로, 행렬의 크기에 비례합니다.
• 공간 복잡도: 최악의 경우 O(M × N) — 재귀 호출 스택이 화면 전체 크기만큼 깊어질 수 있습니다.

마무리

플러드 필 알고리즘은 그림판 프로그램의 '영역 채우기' 기능, 이미지 처리에서의 배경 제거, 미로 찾기 문제 등 다양한 분야에서 활용됩니다. 재귀를 이용한 DFS 방식 외에도 큐(queue)를 사용하는 BFS 방식으로 구현할 수 있으며, 매우 큰 화면에서는 스택 오버플로우를 피하기 위해 BFS 방식이 선호되기도 합니다.