Cheese

1. 문제

2. 문제 분석

위의 문제에서 쓰이는 알고리즘이 흡사 스타크래프트에서 저그의 크립이 없어지는 알고리즘과

같을 것이라는 생각이 들지 않는가?

그리고, 이 문제는 앞에서 했던 "두더지 굴" 문제를 응용할 것이다.

아래와 같이 치즈가 놓여져 있는 이차원 배열이 있다고 가정해보자.

치즈가 놓여져있는 공간은 1, 없으면 0 .

첫 번째로 우리는 탐색 지점을 배열의 첫 번째 인덱스라고 가정하겠다. (0,0)이 초기값

탐색 방향은 편의상 "아래->오른쪽->위 -> 왼쪽" 이라고 하겠다.

처음에 시작점에 도착했는데, 치즈가 없는 공간이었다. 이 부분을 -1로 세팅을 한다.

그리고, 탐색을 해보자.

탐색은 치즈가 놓여있지 않은 곳을 시작으로 탐색을 한다. (재귀 호출을 이용해서.)

다만 탐색을 진행하다가 탐색할 영역이 치즈가 놓여져 있는 공간이면,

값만 1씩 누적 합을 한다. (그 이유는 아래에서 다룬다.)

​

문제의 핵심은 아래와 같다.

탐색의 시작 지점은 반드시 치즈가 없는 빈 공간을 시작으로 탐색을 시작한다.

치즈가 없는 비어있는 공간이면 -1로 세팅을 하고, 탐색할 공간이 치즈가 있는 공간이면

그 공간에 값을 1을 누적 합을 한다. (치즈가 있는 공간이면 값만 1씩 누적 증가시킨다. )

그러면, 탐색을 쭉 하고 나면 아래와 같은 그림이 된다.

[그림 1]

그리고, 녹아야 할 치즈를 찾는 일만 남았다.

이는 단순하다. 먼저 치즈가 없었던 공간이 현재는 -1로 세팅이 되었는데, 다시 0으로 두자.

그리고, 녹아야 할 치즈의 규칙은 간단하다. 2를 초과한 숫자는 모두 녹아야 할 치즈들이다.

나머지 2를 초과하지 않은 치즈들은 다시 1로 세팅을 해 두는 것이다.

세팅을 해보자.

[그림 2]

위와 같이 세팅이 된다.

위에서 왜 탐색할 위치가 치즈가 있는 공간이면 값만 올리는 방식을 택했냐면

[그림 1]을 보면 안쪽에 있는 0은 -1로 바뀌지 않게끔 하므로써, 모퉁이에 있는 치즈만 없애기 위해서 그런 것.

그러면 아직 치즈가 남아있기 때문에 위와 같은 과정을 다시 반복해서, 치즈의 남은 양이 0이 될 때까지 계속 하면 된다.

 

<보충설명>

[그림 1]을 다시 가져오면 아래와 같다.

위의 그림에서 노란색 박스의 치즈가 있는 공간과 주황색 박스가 있는 치즈의 공간을 살펴보자.

치즈가 없는 공간에서, 치즈가 있는 공간을 탐색 시에 값을 1씩 누적시키는 조건만 들어가면

노란색 영역을 탐색하는 횟수는 3번이다. 반면에 주황색 영역은 1번 밖에 없다.

즉, 모퉁이에 놓인 치즈는 값이 2를 초과할 수 밖에 없다.

반면에 안쪽에 놓인 치즈는 값이 1 혹은 2 값만 취할 수 밖에 없다.

 

3. 구현

프로그램 실행결과

4. 소스 파일

Cheese.c

0.01MB

5. 위에서 수정해야 할 점

위에서 탐색을 (0,0)으로 고정을 하고 탐색을 시작하는데,

만약 (0,0)에 치즈가 놓여있다면 문제가 발생한다.

그 이유는 우리는 치즈가 없는 공간을 찾아 그 위치부터 탐색을 시작해나가기 때문이다.

그렇기 때문에 이에 대한 처리가 필요하다.

전역 변수로 아래의 두 변수를 선언한다.

그리고, 두 변수는 아래의 함수를 호출해서 비어 있는 공간을 찾아 그 위치를 기록한다.

FindEmptyPos함수는 아래의 메인함수에서 호출된다.

프로그램 실행결과

6. 수정한 소스 파일

Cheese.c

0.01MB