플러드 필(Flood Fill) - BFS , DFS

다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘

그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일하다.

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

 

BFS는 큐로 , DFS는 스택으로 구현 할 수 있다.

BFS, DFS는 그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘으로, 다차원 배열이 그래프 자료구조의 특수한 형태이기 때문에 다차원 배열에서도 BFS와 DFS를 사용할 수 있다.

 

BFS 과정

 

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

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

3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다.

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

 

* 모든 칸이 큐에 1번 씩만 들어감이 보장되므로 시간복잡도는 칸이 N개일 때 0(N)입니다.

 

예는 여기서 보기

https://blog.encrypted.gg/729

[실전 알고리즘] 0x05강 - BFS, DFS_구버전

DFS 과정

 

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다. 

2. 스택에서 원소를 꺼내 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 3번 행동을 한다.

3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 넣는다. 

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

 

* 모든 칸이 큐에 1번 씩만 들어감이 보장되므로 시간복잡도는 칸이 N개일 때 0(N)입니다.