[Algorithm] Lake Counting(POJ No.2386)

Lake Counting(POJ No.2386)

문제 : 

크기가 N X M인 정원이 있다. 그 곳에 비가내려 물 웅덩이가 생겼다. 물 웅덩이는 주위(8군데)가 근접하여 있으면 서로 연결되어 있다고 간주한다 . 즉 하나의물 웅덩이로 간주한다. 전부 몇개의 물 웅덩이가 있는지 계산하는 알고리즘을 작성하라.

예시 : 

*    *   *

*   W   *

*    *   *

와 같이 *이 있는 8방향에 W가 있다면 하나의 물 웅덩이로 생각한다. 

N X M 의 필드를 만들어서 초기화 한다. 그리고 초기화 값을 출력한다.

필드에서 물 웅덩이(W)를 찾는다. 찾을시 dfs 함수를 호출한다.

dfs 함수가 호출 되면 'W'를 '.'으로 초기화 시키며 해당 배열값을 중심으로 8방향을 검사한다. 

검사중 'W'가 존재 한다면 다시 dfs 함수를 호출한다.(재귀)

 

결과값

물 웅덩이를 랜덤으로 생성 후 개수를 체크 하였다. 

그리고 체크 할 때에는 재귀함수를 이용하였다.