두더지 굴

1. 들어가기에 앞서

아래의 두더지 굴 문제에 들어가는 알고리즘을 Floud Fill 알고리즘이라 한다.

이 방식은 우리가 많이 한 "지뢰찾기"게임에서 쓰인다.

아래의 문제에서도 나왔다시피 "1이 상하좌우로 연결되어 있으면" 이라는 표현이 나오는데,

상하좌우란 의미가 곧, 탐색 방향이 네방향이다라는 사실을 알 수 있다.

 

2. 문제

3. 문제 분석

주어진 문제에서 가장 첫 번째로 해야할 일은 두더지 굴을 하나 찾아내는 함수를 만들어야 한다.

이 함수의 이름을 SearchDFS라고 하겠다.

함수 이름처럼 "이 우선 탐색"을 해서 하나의 굴을 찾는 함수이다.

하나의 굴을 찾았으면, 처음에 할 일은 두더지굴의 넘버링을 붙여주는 것이다.

그리고, 이 함수의 리턴형을 결정해주어야 하는데, 하나의 굴을 찾아서 알게되는 것은

이 굴의 길이를 알 수 있겠다. 그러므로, 함수의 리턴형은 void가 아닌, int형이 되면 좋겠다.

 

자. 굴이 시작하는 장소에 왔으니까, 굴을 탐색하면 된다.

위에서 언급했듯이, "상,하,좌,우"로 움직여가면서 탐색을 하면 된다.

그런데, 조건이 있다. 탐색을 할 곳이 배열 범위를 넘어가면 안되며,

두더지 굴이 있는 곳으로만 이동을 해야한다.

만약, 탐색을 하다가 0을 만나면 다시 되돌아 와야 한다. <- 재귀함수의 탈출 조건

 

아래의 그림처럼 우리가 이차원배열의 원소인 (i,j)까지 열심히 탐색을 마친 상태라고 가정해보자.

위의 그림에서 처럼, 우리가 움직일 수 있는 곳은

( i-1, j ), ( i+1, j ), ( i, j-1 ), ( i, j+1 ) 이다.

아래의 파란색부분이 움직일 수 있는 공간.

저 위의 4방향이 배열의 밖을 넘어가면 안되며, 탐색할 수 있는 공간이여야지 탐색을 하면 된다.

의사 코드를 작성해보자.

 

4. 구현

 

프로그램 실행결과

 

5. 소스 파일

main.c

0.00MB

 

그런데, 문제에서 보면 두더지 굴의 수와 그리고, 각 두더지 굴의 크기를 내림차순으로 출력을 해야한다.

기본적인 정렬 알고리즘은 버블 정렬을 이용하겠다.

그리고 각 두더지 굴의 크기를 저장할 변수를 배열로 선언하고 이는 전역 변수로 두겠다.

아래는 추가로 만든 함수이며, 메인 함수에서 호출된다.

위의 함수는 아래에서 호출된다.

 

프로그램 실행결과

 

최종 소스 파일

main.c

0.00MB

 

 

 

이 문제는 DFS아닌 BFS 방식으로 구현할 수 있다.

designatedroom87.tistory.com/72?category=885506

두더지 굴