Flood Fill 은 격자 (grid) 또는 이미지에서 특정 위치와 연결된 같은 색 영역을 모두 칠하는 알고리즘. 그래픽 소프트웨어의 “페인트 버킷 (paint bucket)” 도구의 핵심.
DFS 또는 BFS 로 4방향 / 8방향 연결된 칸을 탐색. O(N × M) (격자 크기).
문제 상황과 동기
격자 / 이미지에서 “클릭한 위치와 같은 색으로 연결된 모든 픽셀을 새 색으로 칠하기”.
naive: 전체 격자 순회 (O(N × M)), 매번 연결 확인. 중복 탐색 심함.
flood fill: 시작점에서 BFS/DFS 로 연결된 칸만 방문. O(N × M) (worst case 전체 격자).
핵심 통찰: 격자의 연결 영역 (connected component) 을 찾는 것. 그래프 탐색 (BFS/DFS) 의 격자 버전.
응용:
그래픽 소프트웨어 (페인트, 포토샵)
게임 (지뢰 찾기의 빈 칸 펼치기, 지형 생성)
PS (섬 개수, 영역 크기, 둘레)
시각화
핵심 아이디어
invariant: 방문한 칸 (x, y) 는 시작점과 같은 색으로 연결됨.
flood_fill(x, y, old_color, new_color): if out_of_bounds(x, y) or visited[x][y] or grid[x][y] ≠ old_color: return grid[x][y] = new_color visited[x][y] = true for (dx, dy) in directions: # 4방향 또는 8방향 flood_fill(x + dx, y + dy, old_color, new_color)
DFS vs BFS:
방식
장점
단점
DFS (재귀)
코드 간결
스택 오버플로우 위험 (깊은 재귀)
BFS (큐)
스택 안전, 거리 계산 가능
코드 약간 길어짐
대부분 BFS 권장 (격자 크기 클 때 안전).
알고리즘
DFS (재귀)
flood_fill_dfs(grid, x, y, old_color, new_color): if x < 0 or x >= n or y < 0 or y >= m: return if grid[x][y] ≠ old_color: return grid[x][y] = new_color flood_fill_dfs(grid, x+1, y, old_color, new_color) # 하 flood_fill_dfs(grid, x-1, y, old_color, new_color) # 상 flood_fill_dfs(grid, x, y+1, old_color, new_color) # 우 flood_fill_dfs(grid, x, y-1, old_color, new_color) # 좌
BFS (큐)
flood_fill_bfs(grid, sx, sy, old_color, new_color): if grid[sx][sy] ≠ old_color: return queue q q.push((sx, sy)) grid[sx][sy] = new_color while q not empty: (x, y) = q.pop() for (dx, dy) in directions: nx = x + dx, ny = y + dy if valid(nx, ny) and grid[nx][ny] == old_color: grid[nx][ny] = new_color q.push((nx, ny))
구현
// Flood Fill BFS, 격자에서 연결 영역 칠하기#include <bits/stdc++.h>using namespace std;int dx[] = {-1, 1, 0, 0};int dy[] = {0, 0, -1, 1};void flood_fill(vector<vector<int>>& grid, int sx, int sy, int new_color) { int n = grid.size(), m = grid[0].size(); int old_color = grid[sx][sy]; if (old_color == new_color) return; // 같으면 불필요 queue<pair<int, int>> q; q.push({sx, sy}); grid[sx][sy] = new_color; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == old_color) { grid[nx][ny] = new_color; q.push({nx, ny}); } } }}int main() { int n, m, sx, sy, new_color; cin >> n >> m >> sx >> sy >> new_color; vector<vector<int>> grid(n, vector<int>(m)); for (auto& row : grid) for (auto& v : row) cin >> v; flood_fill(grid, sx, sy, new_color); for (auto& row : grid) { for (auto v : row) cout << v << " "; cout << "\n"; }}
# Flood Fill BFS, collections.dequefrom collections import dequeimport sysinput = sys.stdin.readlinedef flood_fill(grid, sx, sy, new_color): n, m = len(grid), len(grid[0]) old_color = grid[sx][sy] if old_color == new_color: return directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] q = deque([(sx, sy)]) grid[sx][sy] = new_color while q: x, y = q.popleft() for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == old_color: grid[nx][ny] = new_color q.append((nx, ny))n, m, sx, sy, new_color = map(int, input().split())grid = [list(map(int, input().split())) for _ in range(n)]flood_fill(grid, sx, sy, new_color)for row in grid: print(" ".join(map(str, row)))
// Flood Fill BFS, Queue<int[]>import java.util.*;import java.io.*;public class Main { static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static void floodFill(int[][] grid, int sx, int sy, int newColor) { int n = grid.length, m = grid[0].length; int oldColor = grid[sx][sy]; if (oldColor == newColor) return; Queue<int[]> q = new LinkedList<>(); q.add(new int[]{sx, sy}); grid[sx][sy] = newColor; while (!q.isEmpty()) { int[] cur = q.poll(); int x = cur[0], y = cur[1]; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == oldColor) { grid[nx][ny] = newColor; q.add(new int[]{nx, ny}); } } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int sx = Integer.parseInt(st.nextToken()); int sy = Integer.parseInt(st.nextToken()); int newColor = Integer.parseInt(st.nextToken()); int[][] grid = new int[n][m]; for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < m; j++) grid[i][j] = Integer.parseInt(st.nextToken()); } floodFill(grid, sx, sy, newColor); for (int[] row : grid) { for (int v : row) System.out.print(v + " "); System.out.println(); } }}
stdin
3 3 1 1 91 1 11 1 01 0 1
결과
9 9 99 9 09 0 1
stdin
2 2 0 0 55 55 5
결과
5 55 5
복잡도
항목
값
시간 (최선)
O(1) - 칸 1개만 칠함
시간 (평균)
O(연결 영역 크기)
시간 (최악)
O(N × M) - 전체 격자가 같은 색
공간
O(N × M) - BFS 큐 / DFS 스택
각 칸 최대 1회 방문. 4방향 / 8방향 탐색이므로 간선 O(N × M).
변형 / 활용
1. 섬 개수 세기
격자에서 1 로 연결된 영역 (섬) 개수.
int count_islands(vector<vector<int>>& grid) { int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { flood_fill(grid, i, j, 0); // 방문한 섬 0 으로 cnt++; } } } return cnt;}
2. 영역 크기 / 둘레
flood fill 하면서 칸 개수 (크기) 와 경계 개수 (둘레) 카운트.
int area = 0, perimeter = 0;void flood_fill_with_metrics(int x, int y) { if (out_of_bounds(x, y) or grid[x][y] != old_color) { perimeter++; // 경계 만남 return; } grid[x][y] = new_color; area++; for (auto [dx, dy] : dirs) flood_fill_with_metrics(x + dx, y + dy);}
int region_id = 2; // 0, 1 은 격자 값for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { flood_fill(grid, i, j, region_id++); } }}
함정
1. old_color == new_color
시작점 색과 새 색이 같으면 무한 루프. 미리 체크.
if (old_color == new_color) return;
2. 스택 오버플로우 (DFS 재귀)
격자가 크고 (N, M > 1000) 전체가 같은 색이면 DFS 재귀 깊이 10^6. 스택 오버플로우. BFS 사용 권장.
3. 중복 방문
같은 칸을 큐에 여러 번 넣으면 시간 초과. 칸을 칠할 때 (큐에 넣을 때) 바로 grid[nx][ny] = new_color 로 마킹.
// 잘못된 코드 (중복 방문)if (grid[nx][ny] == old_color) { q.push({nx, ny}); // 큐에 넣고}// pop 할 때 칠하면 여러 번 들어감// 올바른 코드if (grid[nx][ny] == old_color) { grid[nx][ny] = new_color; // 즉시 칠함 q.push({nx, ny});}
4. 경계 체크
nx >= 0 && nx < n && ny >= 0 && ny < m 빼먹으면 segfault.
💬 댓글