개념 이해하기
플러드 필(Flood Fill) 알고리즘은 그림판 프로그램의 '색 채우기' 도구처럼, 특정 영역 안에 있는 픽셀들을 시작점에서부터 인접한 픽셀로 번져 나가며 새로운 색상으로 덮어쓰는 기법입니다. 이번 글에서는 주어진 사각형의 내부를 플러드 필 알고리즘으로 채우는 방법을 C 언어의 그래픽 함수를 통해 살펴보겠습니다.
입력 예시
rectangle(left = 50, top = 50, right = 100, bottom = 100) floodFill(a = 55, b = 55, NewColor = 12, OldColor = 0)
사각형 (50, 50)~(100, 100) 내부의 점 (55, 55)에서 색 채우기를 시작하며, 기존 색상 0(검정 배경)을 새 색상 12(밝은 빨강)로 바꾼다는 의미입니다.
출력 결과
알고리즘 동작 원리
핵심은 재귀(recursion)입니다. 시작 좌표 (a, b)의 기존 색상 'OldColor'를 'NewColor'로 바꾸고, 상하좌우 인접 픽셀에 대해 같은 작업을 반복 수행하는 함수 floodFill(a, b, NewColor, OldColor)을 정의합니다.
좌표 a 또는 b가 화면 경계를 벗어나면 즉시 종료(return)합니다.
getpixel(a, b)로 읽은 현재 픽셀의 색상이 OldColor와 같다면 새 색상으로 칠하고,
위, 아래, 오른쪽, 왼쪽 네 방향으로 각각 재귀 호출을 진행합니다.
floodFill(a+1, b, NewColor, OldColor);
floodFill(a-1, b, NewColor, OldColor);
floodFill(a, b+1, NewColor, OldColor);
floodFill(a, b-1, NewColor, OldColor);
이처럼 네 방향(상·하·좌·우)만 탐색하는 방식을 4방향(4-way) 플러드 필이라고 하며, 대각선까지 포함해 여덟 방향을 탐색하면 8방향(8-way) 플러드 필이 됩니다. 이미 칠해진 픽셀(NewColor)은 조건문에서 걸러지므로 무한 재귀에 빠지지 않습니다.
전체 예제 코드
// floodfill 알고리즘으로 사각형 내부를 채우는 프로그램
#include <graphics.h>
#include <stdio.h>
// 플러드 필 알고리즘 구현
void flood(int x1, int y1, int new_col, int old_col){
// 현재 픽셀이 old_color인지 검사
if (getpixel(x1, y1) == old_col) {
// 현재 픽셀을 새 색상으로 칠함
putpixel(x1, y1, new_col);
// 아래쪽 픽셀 채우기 위한 재귀 호출
flood(x1 + 1, y1, new_col, old_col);
// 위쪽 픽셀 채우기 위한 재귀 호출
flood(x1 - 1, y1, new_col, old_col);
// 오른쪽 픽셀 채우기 위한 재귀 호출
flood(x1, y1 + 1, new_col, old_col);
// 왼쪽 픽셀 채우기 위한 재귀 호출
flood(x1, y1 - 1, new_col, old_col);
}
}
int main(){
int gd1, gm1 = DETECT;
// 그래픽 모드 초기화
initgraph(&gd1, &gm1, "");
// 사각형 좌표 지정
int top1, left1, bottom1, right1;
top1 = left1 = 50;
bottom1 = right1 = 300;
// 사각형 테두리 그리기
rectangle(left1, top1, right1, bottom1);
// 채우기를 시작할 좌표
int x1 = 51;
int y1 = 51;
// 채워 넣을 새 색상
int newcolor = 12;
// 교체 대상이 되는 기존 색상
int oldcolor = 0;
// 사각형 채우기 함수 호출
flood(x1, y1, newcolor, oldcolor);
getch();
return 0;
}코드 핵심 포인트
- 시작 좌표 선택: 사각형 테두리가 (50, 50)~(300, 300)이므로, 테두리 선에 걸리지 않도록 내부 한 점인 (51, 51)에서 채우기를 시작합니다.
- 종료 조건: getpixel() 값이 old_color(0)가 아니면 더 이상 확장하지 않으므로, 테두리 선을 만나는 순간 채우기가 자연스럽게 멈춥니다.
- 그래픽 라이브러리: graphics.h는 Turbo C 계열(BGI) 컴파일러에서 제공되는 라이브러리로, Code::Blocks 등 최신 환경에서는 WinBGIm 같은 호환 라이브러리를 설치해야 실행할 수 있습니다.
- 성능: 이 알고리즘은 영역 내 모든 픽셀을 한 번씩 방문하므로 시간 복잡도는 O(n)(n은 영역의 픽셀 수)입니다. 다만 깊은 재귀 호출로 인해 큰 영역에서는 스택 오버플로우가 발생할 수 있어, 실무에서는 스택이나 큐를 이용한 반복문 버전이 권장됩니다.
실행 결과
프로그램을 실행하면 화면에 사각형 테두리가 그려지고, 시작점 (51, 51)에서부터 내부 전체가 밝은 빨강(색상 12)으로 차오르는 것을 확인할 수 있습니다.
