플러드 필

컴퓨터 그래픽스 소프트웨어 마지막 수정: 2026-09-02 04:26:41

1. 개요[편집]

플러드 필 Flood Fill
정체	격자 위 연결성분에 대한 DFS/BFS
입력	시드 화소 + 「같은 영역인가」 판정 술어
이웃 정의	4-연결 / 8-연결 (짝을 맞춰야 한다)
복잡도	화소 수에 선형 $O(N)$
대표 사고	재귀 구현의 스택 오버플로
실무형	스캔라인(구간) 플러드 필

페인트통 아이콘을 클릭하는 순간, 여러분은 그래프 탐색 알고리즘 하나를 실행한 것이다.

플러드 필(flood fill, seed fill)은 격자 위의 시드 화소 하나에서 출발해 「같은 영역」 판정 술어를 만족하면서 이웃으로 도달 가능한 모든 화소를 찾아 한꺼번에 바꾸는 알고리즘이다. 그림판의 페인트통, 포토샵의 마술봉, 지뢰찾기에서 빈칸을 눌렀을 때 뻥 뚫리는 그 동작이 전부 이것이다.

알고리즘적으로는 새로울 게 하나도 없다. 화소를 정점, 이웃 관계를 간선으로 보면 격자 그래프의 연결성분을 하나 찾는 문제이고, 깊이 우선 탐색이든 너비 우선 탐색이든 아무거나 쓰면 된다. 그런데도 이 문제에 독립된 이름과 전용 구현 기법이 붙어 있는 이유는 두 가지다 — 격자라서 인접 리스트를 만들 필요가 없고(이웃이 좌표 산술로 나온다), 그리고 화소 수가 수백만이라서 교과서 코드가 그대로 죽기 때문이다.

2. 연결성 — 4냐 8이냐[편집]

화소 $(x,y)$ 의 이웃 정의는 둘 중 하나다.

4-연결: 상하좌우 네 개. 변을 공유하는 이웃.
8-연결: 여기에 대각선 네 개를 더한 여덟 개. 꼭짓점만 공유해도 이웃으로 친다.

취향 문제처럼 보이지만 아니다. 이산 격자에서는 연결성 역설이 있어서, 전경과 배경에 같은 연결성을 쓰면 조던 곡선 정리가 깨진다. 대각선으로만 이어진 한 화소 폭의 닫힌 고리를 생각해 보자. 전경을 8-연결로 보면 이 고리는 닫힌 곡선이지만, 배경도 8-연결로 보면 안쪽과 바깥쪽이 대각선으로 통해 버려 닫힌 곡선이 평면을 나누지 못한다. 반대로 둘 다 4-연결로 보면 고리 자체가 끊어져 있는데 안팎은 분리돼 있는 모순이 생긴다.

그래서 규칙은 하나다 — 전경과 배경은 반드시 서로 다른 연결성을 쓴다(전경 8 / 배경 4, 또는 전경 4 / 배경 8). 이 짝을 안 맞추면 “구멍 개수가 안 맞는다”, “경계 추적이 무한 루프를 돈다” 같은 증상이 나온다. 실무적 함의는 더 단순하다. 8-연결 채우기는 대각선으로 한 화소만 뚫려 있어도 밖으로 샌다. 선을 그은 뒤 안쪽을 칠하려는 사용자 입장에서는 4-연결이 훨씬 안전하고, 그래서 대부분의 페인트 툴 기본값이 4-연결이다.

3. 순진한 구현이 죽는 이유[편집]

교과서 코드는 아름답다.

fill(x, y):
    if 범위 밖 or 이미 방문 or 술어 불만족: return
    화소 (x,y) 를 새 색으로 칠한다
    fill(x+1,y); fill(x-1,y); fill(x,y+1); fill(x,y-1)

그리고 1920×1080 화면을 통째로 칠하는 순간 죽는다. 재귀 깊이가 최악의 경우 화소 수 전체( $2\times10^6$ )까지 가는데, 리눅스 기본 스레드 스택은 8 MB, 윈도는 1 MB다. 프레임 하나에 수십 바이트만 잡아도 감당 가능한 깊이는 $10^5$ 자릿수라 자릿수가 하나 이상 모자란다. 옛날 그래픽 툴에서 큰 영역을 칠하면 프로그램이 통째로 사라지던 현상의 정체가 대체로 이것이다.¹

첫 번째 처방은 명시적 스택 또는 큐로 펼치는 것이다. 힙 메모리는 기가바이트 단위라 깊이 문제가 사라진다. DFS(스택)와 BFS(큐)는 채워지는 순서만 다르고 결과와 복잡도는 같으므로, 진행 애니메이션을 물결처럼 보이게 하고 싶으면 BFS, 메모리 지역성이 조금 낫기를 바라면 DFS를 쓴다.

여기서 놓치기 쉬운 함정 하나. 방문 표시는 스택/큐에 넣을 때 찍어야 한다. 꺼낼 때 찍으면 같은 화소가 이웃 수만큼 중복으로 들어가 스택이 4배로 부풀고, 최악의 케이스에서 메모리가 다시 터진다. 결과는 맞는데 느리고 뚱뚱한, 가장 알아채기 어려운 종류의 버그다.

4. 스캔라인 플러드 필[편집]

명시적 스택으로 바꿔도 여전히 화소 하나당 스택 원소 하나다. 이걸 구간 하나당 원소 하나로 줄이는 것이 스캔라인(span-based) 플러드 필이고, 실무 구현의 사실상 표준이다. 아이디어는 앨비 레이 스미스가 1979년 SIGGRAPH에서 발표한 Tint Fill로 거슬러 올라간다.²

스택에 시드가 속한 가로 구간 정보를 넣는다
while 스택이 비지 않음:
    구간 (x_left..x_right, y) 를 꺼내 그 줄을 통째로 칠한다
    위 줄(y-1)과 아래 줄(y+1)을 x_left..x_right 범위에서 훑으며
        술어를 만족하는 "새 구간"이 시작되는 지점마다 그 구간 하나만 스택에 넣는다

핵심은 두 가지다. 첫째, 가로로 이어진 화소들은 탐색할 필요가 없다 — 한 화소가 영역에 속하면 그 좌우로 술어를 만족하는 동안은 전부 같은 영역이라는 것이 자명하므로, 반복문으로 쭉 밀면 된다. 둘째, 위아래 줄에서 구간의 시작점만 스택에 넣는다. 폭 $w$ 짜리 사각형을 칠할 때 순진한 방식은 스택 원소가 $O(wh)$ 개인데, 스캔라인은 $O(h)$ 개다.

메모리 지역성도 덤으로 좋아진다. 가로 한 줄은 프레임버퍼에서 연속된 주소라 캐시 라인을 통째로 쓰지만, 화소 단위 DFS는 상하좌우로 튀면서 매번 다른 캐시 라인을 건드린다. 실측에서 스캔라인 방식이 몇 배씩 빠른 이유의 절반은 스택 크기가 아니라 이쪽이다.

구현이 지저분해지는 자리는 오목한 영역이다. 위쪽 줄에 구간이 여러 개로 쪼개져 있거나, 이미 칠한 구간의 위로 다시 올라가야 하는 U자 형상에서 구간을 중복해서 넣거나 빠뜨리기 쉽다. 그래서 코드마다 “부모 구간 방향을 기억해 되돌아가는 검사를 생략한다” 같은 변종이 붙어 있고, 이 최적화가 U자 형상에서 조용히 틀리는 것이 이 분야의 전통적인 통과의례다.

5. 경계 채우기와의 대조[편집]

같은 시드 채우기지만 종료 조건이 반대인 형제가 있다.

	플러드 필	경계 채우기(boundary fill)
판정 대상	지금 화소가 원래 색과 같은가	지금 화소가 경계색이 아닌가
채우는 것	시드와 같은 색인 연결 영역	경계선으로 둘러싸인 내부 전부
내부에 다른 색이 섞이면	그 부분은 안 칠해진다	경계색만 아니면 다 칠한다
전형적 용도	마술봉, 색 교체	벡터 도형의 내부 채우기

즉 플러드 필은 “시드와 닮은 것”을 좇고, 경계 채우기는 “경계에 막힐 때까지” 간다. 안이 얼룩덜룩한 도형을 한 색으로 칠하고 싶다면 경계 채우기가 맞고, 그라데이션 배경에서 특정 색만 갈아 끼우고 싶다면 플러드 필이 맞다. 참고로 벡터 그래픽스의 다각형 내부 채우기는 이 둘과 아예 다른 계열이다 — 래스터화 단계에서 감김수나 짝홀 규칙으로 내부를 판정하지 두 발로 걸어 다니지 않는다.

6. 연결성분 레이블링과 유니온 파인드[편집]

플러드 필은 연결성분 하나를 찾는다. 영상 전체의 모든 성분에 번호를 붙이려면 배경 아닌 모든 화소를 시드 삼아 플러드 필을 반복하면 되고, 이러면 전체가 여전히 $O(N)$ 이다. 그런데 고전적인 연결성분 레이블링(Rosenfeld & Pfaltz, 1966)은 다른 길을 간다.

1패스 — 영상을 왼쪽 위부터 래스터 순서로 한 번 훑으며, 이미 지나온 이웃(4-연결이면 왼쪽·위)의 라벨 중 최솟값을 붙인다. 이웃들의 라벨이 서로 다르면 “이 둘은 사실 같은 성분”이라는 동치 관계를 기록해 둔다.
2패스 — 기록해 둔 동치 관계를 유니온 파인드로 합쳐 대표 라벨을 뽑고, 영상을 다시 훑으며 라벨을 대표로 치환한다.

플러드 필 대비 장점이 명확하다. 접근 패턴이 순수 래스터 순서라 스트리밍·SIMD·GPU에 그대로 얹히고, 영상 전체를 메모리에 올릴 필요도 없다. 대신 유니온 파인드 자료구조가 필요하고 두 번 훑는다. 성분 하나만 필요하면 플러드 필, 전부 필요하면 2패스 레이블링 — 이게 대략의 갈림길이다.

한 걸음 더 나가면 분수령 변환이 있다. 뱅상-소이유의 침수 알고리즘은 사실상 우선순위 큐로 순서를 매긴 플러드 필이다. 여러 시드(마커)에서 동시에 물을 차오르게 하되, 낮은 밝기부터 처리하고 서로 다른 라벨의 물이 만나는 자리를 분수선으로 남긴다. 평평한 이진 영상에 시드 하나를 두면 그냥 플러드 필로 퇴화한다. 형태학적 재구성, 구멍 채우기(hole filling), 경계 접촉 객체 제거 같은 수학적 형태학의 도구들도 밑바닥에서는 조건부 팽창, 즉 마스크에 갇힌 플러드 필이다.

7. 게임과 실무에서[편집]

지뢰찾기. 지뢰 인접 수가 0인 칸을 열면 이웃 8칸이 자동으로 열리고, 그중 또 0인 칸이 있으면 연쇄한다. 정확히 8-연결 플러드 필이며, 판정 술어는 “닫혀 있고 깃발이 없다”, 확장 조건은 “인접 지뢰 수가 0”이다. 0이 아닌 숫자 칸은 열되 거기서 멈춘다는 점이 순수 플러드 필과 다른 유일한 지점 — 경계는 방문하되 확장하지 않는 패턴이라, 구현에서는 “칠한다”와 “이웃을 큐에 넣는다”를 분리해야 한다.³
타일 맵 영역 판정. 「이 방과 저 방이 통하는가」, 「플레이어가 갇혔는가」, 「이 물웅덩이의 넓이는」 전부 플러드 필 한 번이다. 절차적 생성 던전에서 고립된 방을 검출하는 것도 마찬가지 — 성분이 하나가 아니면 그 맵은 버리거나 통로를 뚫는다. 파괴 가능한 지형에서 “떨어져 나간 덩어리”를 찾는 것도 같은 루틴이고, 이 경우 매 프레임 전체를 다시 돌리는 대신 바뀐 지점 주변만 국소적으로 재계산하는 것이 관건이다.
뿌요뿌요·비주얼드류. 같은 색 4개 이상이 이어지면 터지는 매칭 판정이 그대로 연결성분 크기 세기다.
경로 계획의 전처리. 시작점과 목표가 같은 성분에 있는지 플러드 필로 먼저 확인하면, 도달 불가능한 목표에 A* 알고리즘을 걸어 맵 전체를 훑고 실패하는 최악의 경우를 피할 수 있다. 메시 생성 결과에서 떠 있는 조각을 잡는 검사도 같은 발상이다.
CFD·해석 전처리. 닫힌 표면 안쪽을 셀로 채우는 복셀화, 유동 도메인에서 외부와 통하지 않는 갇힌 공동(void)을 찾아내는 검사가 격자 위 플러드 필이다. 표면에 화소 하나만큼의 틈이 있으면 채우기가 밖으로 새면서 도메인 전체가 유체가 되어 버리는데, 격자 해석 전처리에서 “왜 셀 수가 이상하지”의 흔한 원인이다.

8. 톨러런스 채우기의 함정[편집]

마술봉이 “비슷한 색까지” 잡는 순간, 얌전하던 알고리즘이 지저분해진다. 판정 술어를 $|c - c_{\text{seed}}| \le \varepsilon$ 로 놓느냐 $|c - c_{\text{이웃}}| \le \varepsilon$ 로 놓느냐부터 다른 물건이 된다.

전역 기준( $c_{\text{seed}}$ 대비) — 결과가 방문 순서에 의존하지 않아 결정적이다. 대신 완만한 그라데이션에서 딱 $\varepsilon$ 만큼 떨어진 자리에 칼로 자른 듯한 경계가 생긴다.
국소 기준(이웃 대비) — 그라데이션을 잘 따라간다. 대신 “비슷하다”는 관계가 추이적이지 않다. $a \approx b$ , $b \approx c$ 여도 $a \not\approx c$ 일 수 있으므로, 어느 화소를 먼저 방문했느냐에 따라 채워지는 영역이 달라진다. DFS와 BFS가 다른 결과를 내는 것이다. 실행할 때마다 결과가 미묘하게 달라지는 툴이 있다면 십중팔구 여기에 병렬화가 얹혀 있다.

부동소수 데이터라면 문제가 하나 더 붙는다. 등식 비교( $c = c_{\text{target}}$ )는 애초에 성립하지 않으므로 톨러런스가 필수인데, NaN이 끼면 모든 비교가 거짓이 되어 그 화소가 조용히 벽 역할을 한다. 부동소수점 연산의 고전적 함정이 채우기 알고리즘에서 “영역이 왜 여기서 끊기지”로 나타나는 사례.

마지막으로 모든 플러드 필 구현이 반드시 밟아 본 버그 하나. 새 색이 원래 색과 같으면 술어가 영원히 참이라 무한 루프에 빠진다. 실무 코드가 함수 첫 줄에서 if (newColor == targetColor) return; 을 검사하는 것은 우아함이 아니라 흉터다. 방문 배열을 따로 두면 이 문제는 구조적으로 사라지지만, 화소당 1비트를 더 쓰기 싫어서 프레임버퍼를 방문 표시로 겸용하려다 생기는 일이다. 안티에일리어싱된 경계에서 반투명 화소가 남아 지저분한 테두리가 생기는 것도 같은 뿌리 — 이건 채운 영역을 한 화소 팽창시키거나 경계에서 알파를 섞어 얼버무리는 것이 실무 처방이다.

9. 관련 문서[편집]

그림 하나 칠하다가 저장 안 한 작업물이 통째로 날아가는 경험은 세대를 초월한 공통 기억이다. 재미있는 것은 이 버그가 작은 그림에서는 절대 재현되지 않는다는 점 — 테스트를 32×32 아이콘으로만 하면 영원히 못 잡는다. “우리 쪽에선 잘 되는데요”의 원형 같은 사례. ↩
Smith, A. R. (1979). “Tint Fill”. SIGGRAPH ‘79. 앨비 레이 스미스는 나중에 픽사 공동창업자가 되는 사람이고, 이 논문은 안티에일리어싱된 경계까지 감안한 채우기를 다뤘다. 즉 40년 전에 이미 “반투명 테두리 어쩔 거냐”가 논점이었다. 우리는 그 문제를 아직도 완전히는 못 풀었다. ↩
참고로 지뢰찾기의 첫 클릭에서 열리는 칸의 개수 분포는 퍼콜레이션 문제와 구조가 같다. 지뢰 밀도가 임계값 아래면 열린 영역이 판 전체를 덮는 거대 성분이 생기고, 위면 잘게 쪼개진다. 초급 판이 시원하게 뻥 뚫리고 고급 판이 답답한 데는 통계물리적 이유가 있는 셈이다. ↩