에듀테크 프로젝트 대시보드
플러드 필 (Flood Fill)
그림판에서 페인트통 버튼을 누르면, 클릭한 지점과 같은 색으로 이어진 영역만
한꺼번에 새 색으로 바뀐다. 이 "번져 나가며 칠하기"가 바로 플러드 필이다.
시작 칸에서 상하좌우(또는 대각선까지) 이웃을 따라가며, 원래 색과 같은 칸이면
새 색으로 바꾸고 그 이웃을 다시 검사한다. 벽이나 다른 색을 만나면 거기서 멈춘다.
큐를 쓰면 BFS, 스택을 쓰면 DFS — 둘 다 결과는 같다.
페인트통 모드 · 캔버스를 클릭(또는 드래그)하세요. 벽 모드에서는 드래그로 검은 벽을 그리고, 같은 곳을 다시 그으면 지워집니다.
# grid[y][x] : 픽셀 색, (sx, sy) : 클릭한 칸, newColor : 새 색 def flood_fill(grid, sx, sy, newColor): old = grid[sy][sx] if old == newColor: return # 이미 그 색이면 무한루프 방지 queue = [(sx, sy)] grid[sy][sx] = newColor while queue: x, y = queue.pop(0) # pop() 이면 DFS(스택) for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]: # 4방향 nx, ny = x+dx, y+dy if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] == old: grid[ny][nx] = newColor # 넣을 때 바로 칠한다 = 중복 방지 queue.append((nx, ny))
왜 재귀 대신 큐/스택인가? 재귀 flood_fill(nx, ny) 는 짧고 우아하지만, 넓은 영역을 칠하면 호출 깊이가 픽셀 수만큼 쌓여 스택 오버플로가 난다. (1000×1000 이미지면 100만 단계.) 그래서 실제 그래픽 프로그램은 명시적 큐/스택이나 스캔라인 방식을 쓴다.
| 방식 | 자료구조 | 퍼지는 모양 | 특징 |
|---|---|---|---|
| BFS (큐) | Queue (앞에서 꺼냄) | 시작점에서 동심원(파도)처럼 | 경계(프론티어)가 커질 수 있어 메모리를 많이 씀 |
| DFS (스택) | Stack / 재귀 | 한 방향으로 길게 뻗은 뒤 되돌아옴 | 코드가 가장 간단하나 재귀는 깊이 폭발 위험 |
| 스캔라인 | 가로 구간(span) 스택 | 가로줄 통째로 칠하고 위·아래 줄만 검사 | push 횟수가 훨씬 적어 실무에서 가장 빠름 |
셋 다 최종 결과(칠해지는 영역)는 완전히 동일하다. 다른 건 순서와 효율뿐. 위 데모에서 알고리즘을 바꿔 가며 같은 영역을 칠해 보면 퍼지는 모양이 확 달라진다.
시작 칸의 색을 기억해 두고, 그와 같은 색으로 이어진 칸만 새 색으로 — 그게 전부다.