[알고리즘 수학] 늑대,염소,양배추 문제

문제 출처) 길벗 - 알고리즘 퍼즐

문제)

늑대 n마리, 염소 n마리, 양배추 n개, 사냥꾼 n명이 있다.

누구도 위험해 지지 않는 방법으로 이들을 한 줄로 세우는 방법을 찾아야 한다. 즉 사냥꾼 옆에 늑대가 있다면 사냥꾼은 늑대를 총으로 쏘아서 죽일 것이고 늑대 옆에 염소가 있다면 늑대는 염소를 잡아 먹을 것이고 염소 옆에 양배추가 있다면 양배추는 염소에게 먹힐 것이다.

또한 같은 종류 끼리는 서로 인접하지 않아야 한다. 즉 사냥꾼과 사냥꾼이 같이 있으면 안된다.

이 문제의 해를 구하는 알고리즘을 설계하시오.

 

문제 풀이)

먼저 n = 1인 경우 다음과 같이 생각 할 수 있다.

첫번째 : 늑대,염소,양배추,사냥꾼이 나오는 각각의 경우를 생각해 보자.

늑대-양배추-사냥꾼-염소

염소-사냥꾼-양배추-늑대

양배추- 어떤것이 나와도 문제 발생

사냥꾼-어떤것이 나와도 문제 발생

즉 늑대와 염소가 떨어져 있고 가운데에 사냥꾼과 양배추가 순서대로 끼워져 있어야 함을 알 수 있다.

 

다음으로 n=2 인 경우를 생각해 보자.

늑대-양배추-사냥꾼-염소 다음으로 나올 수 있는 경우는 사냥꾼 밖에는 없다. 그 다음 사냥꾼 다음으로 나올 수 있는 것은 양배추 밖에 없다. 그 다음은 늑대 밖에는 없다. 그 다음 염소가 나오면 잡혀 먹힌다.

염소-사냥꾼-양배추-늑대 다음으로 나올 수 있는 경우 역시 양배추 밖에는 없다. 그 다음은 사냥꾼,염소 다음 늑대가 나오면 염소는 잡아 먹힌다.

n=1 인 경우의 뒤에 붙이는 경우는 없음을 알 수 있다.

그렇다면 다음과 같이 가운데 끼워 넣는 방법을 생각해 보자.

늑대-양배추-늑대-양배추-사냥꾼-염소-사냥꾼-염소

염소-사냥꾼-염소-사냥꾼-양배추-늑대-양배추-늑대

2가지가 가능함을 알 수 있다.

여기서 문제의 핵심은 염소 옆에는 사냥꾼만 존재 할 수 있고 늑대 옆에는 양배추만 존재 할 수 있다는 것이다.

위의 두가지 풀이 외에 다른 풀이가 존재하지 않는 다는 것을 증명해 보자.

위에 있는 것과 다른 답이 존재한다고 가정을 해 보자.

염소와 늑대가 양 끝에 있지 않고 안에 들어가는 경우를 생각해 보자.

그렇다면 늑대 옆에 반드시 양배추가 있어야 하는데 양배추-늑대-양배추 와 같은 형태가 되므로 늑대 보다 양배추가 1개 더 많아야 한다. 따라서 모순이 된다.

 

따라서 문제의 정답은 n의 값과 무관하게 2가지이다.