Flood fill
위키백과 ― 우리 모두의 백과사전.
Flood fill 혹은 seed fill이라고 불리는 이 알고리즘은 다차원 배열에서 지정된 위치와 연결된 부분을 결정하는 알고리즘이다. 어도비 포토샵과 같은 그림 프로그램에서 화면에 색을 칠하는 기능에 사용된다. 그 외에도 뿌요뿌요, 루미네스 등과 같은 퍼즐 게임에도 사용된다.
Flood fill 알고리즘은 일반적으로 시작 노드, 목표 색깔, 대체 색깔이라는 세 개의 파라미터를 받아들인다. 이 알고리즘은 시작 노드와 연결된 배열의 모든 노드를 따라가며 목표 색깔을 대체 색깔로 바꾸어 나간다. Flood fill 알고리즘을 구현하는 방법은 여러가지가 있지만, 대부분 큐나 스택과 같은 자료구조를 사용한다. 다음은 스택을 기반으로 하여 재귀적 방식으로 구현한 예이다.
Flood-fill (노드, 목표 색상, 대체 색상):
1. 노드의 색이 목표 색상이 아니면 종료
2. 노드의 색을 대체 색상으로 변경
3. Flood-fill(노드의 왼쪽, 목표 색상, 대체 색상) 수행
Flood-fill(노드의 오른쪽, 목표 색상, 대체 색상) 수행
Flood-fill(노드의 위쪽, 목표 색상, 대체 색상) 수행
Flood-fill(노드의 아래쪽, 목표 색상, 대체 색상) 수행
4. 종료
