[DFS] flood fill ( p.78 )

 

이와 같이 그래프로 만든 다음 배열의 (0, 0)부터 순차탐색을 진행하면서 (a, b)의 값이 만약 1이라면 이 점을 시작으로 하여 깊이우선탐색을 이용하여 모든 연결된 점을 방문하고 특정 값으로 체크한다.

나머지 점들도 모두 순차탐색하면서 마지막 까지 깊이우선탐색을 실행하고 알고리즘을 종료한다. 마지막에 깊이우선탐색을 실행한 횟수가 두더지의 수가 되고, 각 두더지 굴의 크기는 다른 배열에 저장해 둔 다음 마지막에 std::sort()를 이용하여 정렬한 후 내림차순으로 출력하면 된다.

 

여기에 사용되는 알고리즘은 지뢰찾기, 뿌요뿌요 등의 게임에 많이 활용되는 방법으로서, flood fill이라고도 한다. 자주 등장하는 방법이므로 익혀두면 활용가치가 크다.

 

이 알고리즘에서는 재귀함수를 이용하여 깊이우선탐색을 구현한다. 이때 가장 조심해야 할 점은 재귀의 깊이가 너무 커지면 runtime error가 발생할 수도 있다는 것이다. 일반적으로 release 모드라면 재귀의 깊이는 대략 10만 내외가 된다. 이 문제에서는 관계없지만 깊이가 너무 크다고 판단되면 다음 절에서 배울 너비우선탐색으로 처리하거나, 재귀 대신 스
택을 이용해도 된다.