[코딩문제] 용병과 식인종

Write a program that solves the following problem: Three missionaries and three cannibals
come to a river and find a boat that holds two people. Everyone must get across the
river to continue on the journey. However, if the cannibals ever outnumber the missionaries
on either bank, the missionaries will be eaten. Find a series of crossings that will
get everyone safely to the other side of the river.

 

다음 문제를 해결할 프로그램을 짜라 : 세 명의 용병과 세 명의 식인종이 2명을 태울 수 있는 보트가 있는

강에 도착했다. 여정을 계속하기 위해 하나도 빠짐없이 강을 건너야 한다. 그런데, 만약에 강 한쪽 편에

식인종의 수가 용병의 수보다 많을 경우, 그 쪽 용병은 잡아먹힐 것이다.

모두가 안전하게 강 건너편으로 건널 수 있는 일련의 행동을 찾아라.

 

마찬가지로 Resursion으로 풀었다.

여기서도 행동할 수 있는 가짓 수는 5개.

1. 보트를 옮긴다.

2. 용병을 태운다

3. 용병을 내린다.

4. 식인종을 태운다.

5. 식인종을 내린다.

 

이번에는 성공했을 때 행동들을 저장해두어야 한다.

 

각 행동들을 나타내는 함수들이다.

 

recursive 호출을 할 함수이다. 

강 왼편에서 우측으로 간다고 상정하고

lm = left mercenary

lc = left cannibal

rm, rc = right mercenary, cannibal

b = boat 위치

ob = boat에 타고있는 사람 수. tuple로 ob[0]은 용병 수, ob[1]은 식인종 수이다.

m은 일련의 행동들을 저장해두는 list이다.

 

0 : 보트 움직이기

1, 2 : 용병 태우기, 내리기

3, 4 : 식인종 태우기, 내리기

 

 

컴퓨터가 찾아낸 행동의 순서를 살펴보자.

 

1. 먼저 식인종을 태운다

2. 용병을 태운다

3. 건너편에 가서 용병을 내린다.

4. 다시 이쪽으로 와서 식인종을 태운다.

5. 건너편에 식인종을 내린다 (보트에는 식인종이 1명 계속 타고 있음)

6. 와서 용병을 태운다

7. 건너편에 용병을 내린다

8. 이쪽에서 식인종을 태운다

9. 건너편에서 식인종을 내린다

10. 다시 와서 용병을 태운다

11. 건너편에 내린다

12. 식인종을 태운다(?)

13. 식인종을 둘다 내린다.

 

위와 같이 코딩을 하게 되면 n명의 용병과 m명의 식인종에 대해서 문제를 해결할 수 있다.

대신 n 은 m 이상.

 

예를 들어 용병 5명에 식인종 4명일 경우