플러드 필(flood fill)

플러드 필(flood fill) 혹은 시드 필(seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. - 위키백과

위와 같은 다차원 배열이 있다고 가정했을 때, 검은색으로 칠해진 부분은 연결되지 않은 영역이라고 하자.

그러면 위의 다차원 배열에 대해서 특정 칸과 연결된 영역을 찾고 싶을 때 플러드 필 알고리즘을 이용해서 찾을 수 있다. (연결된 영역은 상하좌우로 접근 가능한 경우이다)

 

만약 0.0과 연결된 영역을 찾는다면 아래와 같은 영역이 찾아진다.

또한 0.3과 연결된 영역을 찾으면 아래와 같은 영역이다.

이렇게 연결된 영역을 찾고 싶을 때 사용할 수 있는 알고리즘이 플러드 필 알고리즘이다.

 

스택 기반이나 큐 기반으로 구현할 수 있다.

 

자세한 사항은 아래 위키백과를 참조하자.

reference:

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

플러드 필 - 위키백과, 우리 모두의 백과사전