플러드필 시각화
페인트 버킷처럼 클릭해서 BFS/DFS 영역 채우기 알고리즘을 배우세요
탐색★☆☆
속도
1 / 1그리드를 클릭하면 해당 위치에서 플러드필을 시작합니다
채운 셀: 0큐 크기: 0
채울 색 선택
그리드 크기15 x 20
채울 색탐색 대기현재 셀
BFS 플러드필은 큐(FIFO)를 사용하여 시작점에서 동심원처럼 퍼져나가며 같은 색 영역을 채웁니다.
그리드의 아무 셀이나 클릭하면 플러드필이 시작됩니다.
플러드필이란?
플러드필(Flood Fill)은 이미지 편집 프로그램의 페인트 버킷 도구에 사용되는 알고리즘입니다. 시작 위치에서 인접한 같은 색 셀을 모두 새로운 색으로 채웁니다. BFS로 구현하면 파도처럼 퍼지고, DFS로 구현하면 한 방향으로 깊이 파고듭니다.
사용 방법
- 1원하는 채울 색을 팔레트에서 선택하세요
- 2그리드의 아무 셀이나 클릭하면 플러드필이 시작됩니다
- 3BFS 또는 DFS 모드를 선택해 탐색 방식을 비교하세요
- 4재생 버튼으로 단계별 채우기 과정을 관찰하세요
- 5랜덤/체커보드/섬 패턴 버튼으로 다양한 그리드를 실험하세요
동작 원리
- 1시작 픽셀의 색상을 기록(oldColor)하고, 시작 픽셀을 새 색상으로 변경합니다.
- 2BFS 방식: 큐에 시작점을 추가하고, 큐에서 꺼낸 픽셀의 상하좌우 이웃을 검사하여 oldColor인 경우 새 색상으로 변경하고 큐에 추가합니다.
- 3DFS 방식: 스택/재귀를 사용하여 한 방향으로 깊이 파고들면서 같은 색 영역을 채웁니다.
- 4큐(또는 스택)가 빌 때까지 반복하며, 방문한 셀은 다시 처리하지 않습니다.
실무 활용
- •이미지 편집(Photoshop, GIMP)의 페인트 버킷/매직 완드 도구의 핵심 알고리즘입니다.
- •게임의 지형 채우기(Minecraft 물 흐름, 마인스위퍼 빈 칸 자동 열기)에 사용됩니다.
- •의료 영상의 장기/종양 영역 분할(Segmentation)과 지리정보시스템(GIS)의 등고선 영역 분류에 활용됩니다.
- •회로 기판 설계의 연결 영역 분석과 바둑/오목의 돌 영역 계산에도 쓰입니다.
비슷한 알고리즘
- •BFS 방식 vs DFS 방식 — BFS는 레벨별 확산으로 자연스러운 채우기 애니메이션을 보입니다. DFS(재귀)는 깊은 영역에서 스택 오버플로 위험이 있습니다.
- •연결 컴포넌트 라벨링 — 플러드필의 일반화로 이미지의 모든 연결 영역에 고유 라벨을 부여하는 컴퓨터 비전 기법입니다.
- •Watershed 알고리즘 — 영상 분할에 특화된 고급 플러드필 변형으로 경계 영역을 보다 정밀하게 분리합니다.
학습 팁
- •BFS는 시작점에서 원형으로 퍼지며 채웁니다
- •DFS는 뱀처럼 구불구불하게 깊이 파고들며 채웁니다
- •채워진 셀 수는 같지만 탐색 순서가 다릅니다
- •체커보드 패턴은 인접 셀이 항상 다른 색이라 1칸만 채워집니다
- •이 알고리즘은 Photoshop 페인트통, 지뢰찾기 빈 칸 열기에 사용됩니다
자주 묻는 질문
Q. BFS와 DFS 중 어느 것이 더 빠른가요?
A. 채우는 셀 수는 동일합니다. BFS는 최단 경로 순으로 채우고, DFS는 스택 오버플로 위험이 있어 반복적 구현(스택 사용)이 권장됩니다.
Q. 실제 어디에 사용되나요?
A. 이미지 편집(페인트 통 도구), 지뢰찾기(빈 칸 열기), 게임 맵 탐색, 연결 영역 레이블링, 바둑/오목 영역 계산 등에 사용됩니다.
Q. 대각선 방향도 채울 수 있나요?
A. 4방향(상하좌우) 대신 8방향을 이웃으로 정의하면 됩니다. 페인트 프로그램에서는 보통 8방향을 사용합니다.