플러드 필(Flood Fill) 알고리즘

플러드 필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일하다.

플러드 필 문제는 BFS/DFS 알고리즘으로 풀 수 있다.

 

[BFS의 풀이과정]

1. 시작하는 칸을 큐에 넣고 방문 표시를 한다.

2. 큐에서 원소를 꺼내어 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 탐색을 한다.

3. 해당 칸을 이전에 방문했다면 무시하고, 처음 방문했다면 방문 표시를 하고 해당 칸을 큐에 넣는다.

4. 큐의 모든 원소가 빌 때까지 2를 반복한다.

5. 모든 칸이 큐에 1번씩만 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다.

 

※ 참고 : https://blog.encrypted.gg/941