식인종과 선교사 게임 - sig-injong-gwa seongyosa geim

(사진 출처 : http://www.plastelina.net/games/game2.html 링크를 타고 실제로 게임을 해 볼 수 있다.)

 정원이 2명인 배로 선교사 3명과 식인종 3명이 강을 건너가야한다. 그런데 문제는... 식인종 수가 선교사 수보다 많으면 선교사가 잡아먹힌다. 어떻게하면 모두 무사히 강을 건널 수 있을까?

풀이

접기

 강건너기문제에서 답을 찾기 쉬운 방법은 '중간점 찾기'라고 생각한다.

 이것이 무슨 이야기인고하니, 왼쪽에서 오른쪽으로 가는 것과 오른쪽에서 왼쪽으로 가는 것이 대칭적이기 때문에 사람들이 배를 타고 움직이는 방법 역시 대칭적으로 나올 것이라고 생각하는 것이다. 그럴 경우 필연적으로 대칭 포인트가 중간이 있을 것이므로 첫 상태에서 중간점까지만 생각하면 남은 부분은 대칭적으로 움직이게하면 된다는 것이다.

 이해를 위해 이 문제를 가지고 설명하면,

선교사,식인종|        (선교사,식인종)       |선교사,식인종

이렇게 사람들이 위치할 때 좌로 보나 우로 보나 똑같으므로 대칭의 중간이라고 볼 수 있는 것이다.

 실제로 해답은 다음과 같다.

(선교사 : M , 식인종 : C)

                |            (    )|CCCMMM

                |            (CC)|CMMM

                |(CC)            |CMMM

C              |(C  )            |CMMM

C              |            (C  )|CMMM

C              |            (CC)|MMM

C              |(CC)            |MMM

CC            |(C  )            |MMM

CC            |            (C  )|MMM

CC            |            (MM)|CM

CC            |(MM)            |CM

CM            |(CM)            |CM

CM         |     (CM)    |CM

CM            |            (CM)|CM

CM            |            (MM)|CC

CM            |(MM)            |CC

MMM         |(C  )            |CC

MMM         |            (C  )|CC

MMM         |            (CC)|C

MMM         |(CC)            |C

MMMC      |(C  )             |C

MMMC      |             (C  )|C

MMMC      |             (CC)|

MMMC      |(CC)             |

MMMCCC |(    )              |

공유하기

게시글 관리

저작자표시 비영리 동일조건

'절차 퍼즐' 카테고리의 다른 글

기본 내용은 간단하다. 강혹은 건너야하는 것이라면 그것이 무엇이든지을 사이에 두고 적게는 하나의 무리부터 많게는 서너무리들까지 반대편에 전부 옮기는 것. 그 과정까지의 바리에이션은 너무 많아서 정리하기가 좀 힘들다. 다른 두 종이 타면 한 쪽이 먹힌다든가, 배는 꼭 한명 이상이 있어야 하는 등, 원한다면 필요한 제약을 맘대로 넣으면 되는 만능 퀴즈. 노를 저을 수 있는 사람들을 제한하거나 운송수단을 여러개로 늘리는 등의 응용 문제들도 있다.

3. 문제 1 - 늑대, 양, 풀[편집]

무한도전 스피드 특집에도 나왔던, 가장 유명한 패턴. 늑대, 양, 풀이 있는데 한 번에 하나씩 밖에 옮길 수 없고, 사람이 없으면 늑대는 양을, 양은 풀을 먹어버린다. 모두 무사히 건너기 위해서는 어떻게 해야할까?

먼저 양을 싣고 건너간 뒤, 양을 내리고 혼자 돌아온다. 그리고 늑대 혹은 풀을 싣고 건너간 뒤, 양을 데리고 돌아오는 것. 그리고 양을 내려놓고 나머지 하나를 싣고 건너간 뒤, 혼자 돌아와서 다시 양을 데리고 건너가는 것이다.[랜들먼로의해답]

예전에 나온 수수께끼 책에는 "한 사람이 쌀, 닭, 여우를 가지고 가다가 조그마한 강을 만났다. 그런데 그 강에 걸린 다리가 약하기 때문에 한꺼번에 모두 가지고 건널 수가 없어 무엇이든지 한 가지씩만 가지고 가야 되는데, 여우를 먼저 가지고 건너려면 닭이 쌀을 먹겠고, 쌀을 먼저 가지고 건너려면 여우가 닭을 잡아 먹겠다, 도대체 어떻게 했으면 좋겠는가?"라는 내용의 수수께끼가 있다. 여기서는 늑대가 여우로, 양이 닭으로, 풀이 쌀로 치환되었을 뿐이므로 풀이법은 같다.

4. 문제 2 - 식인종과 선교사[편집]

선교사와 식인종이 각각 3명씩 있으며 강을 건너려고 한다. 선교사가 식인종보다 많거나 같으면 문제가 없지만, 식인종이 선교사보다 많아지면 식인종은 선교사를 먹는다. 또한 배에는 종류를 막론하고 2명까지 탈 수 있다. 아무도 죽지 않으면서 모두 강을 건너려면 어떻게 해야 할까?

먼저 식인종 1명과 선교사 1명이 배를 타고 가되, 식인종을 두고 선교사만 돌아온다(식인1). 다시 식인종 2명이 배를 타고 가서, 식인종이 1명만 내리고 다른 1명이 돌아온다(식인2). 이번에는 선교사 2명이 배를 타고 가서, 선교사가 1명만 내리고 식인종과 함께 돌아온다(식인1, 선교1). 이후 선교사 2명이 가서 모두 내린다(식인1, 선교3). 이후엔 먼저 가 있던 식인종 혼자서 남은 식인종을 1명씩 데려오면 끝.

아래와 같이 배가 11번 왔다갔다한다. C는 식인종, M은 선교사. (출발지점) - (강 건너편) 순으로 서술.
0. C C C M M M - 없음 (초기상태)
1. C C M M - C M (선교사 1명과 식인종 1명이 강을 건넌다)
2. C C M M M - C (선교사 1명만 되돌아온다)
3. M M M - C C C (식인종 2명이 강을 건넌다)
4. C M M M - C C (식인종 1명만 되돌아온다)
5. C M - C C M M (선교사 2명이 강을 건넌다)
6. C C M M - C M (선교사 1명과 식인종 1명이 되돌아온다)
7. C C - C M M M (선교사 2명이 강을 건넌다)
8. C C C - M M M (식인종 1명이 되돌아온다)
9. C - C C M M M (식인종 2명이 강을 건넌다)
10. C C - C M M M (식인종 1명이 되돌아온다)
11. 없음 - C C C M M M (식인종 2명이 강을 건넌다)

이 문제의 핵심은 아무 문제 없이 이동할 수 있는 조건을 찾는 것이다. 즉, 다른 요소에 영향을 주지 않는 요소를 찾는 것. 1번 사례의 경우 양이, 2번 사례의 경우 식인종 1명과 선교사 1명이 해당한다. 특히 2번 사례에서는 '식인종과 선교사가 함께 이동해야' 양쪽의 머릿수가 같아진다는 점이 핵심.

5. 문제 3 - 질투심 많은 남편들[편집]

세 부부가 강을 건너려 하였다. 강에는 작은 쪽배 하나만 있으며 유심히 살펴본 결과 쪽배는 최대 2명이 탈 수 있다는 것을 알아냈다. 그런데 이들 부부 중 남편들은 모두 질투심이 매우 심해 자신의 아내가 자기가 없을 때 다른 남자와 같이 있는 꼴을 못 봤다. 다행인 점은 6명 모두 노를 잘 저을 수 있다. 세 부부가 큰 일 없이 강을 건너려면 어떻게 해야 할까?

일단 아내들만 강 저편으로 보낸다. 그러면 아내 중 한 명이 배를 타고 돌아와야 한다. 그러면 해당 인물의 남편을 제외한 다른 남편들이 배를 타고 강 건너편으로 가면 두 쌍의 부부는 강 건너편에 있고 한 쌍의 부부만 아직 건너지 않은 쪽에 있다. 그런다음 강 건너편의 부부 중 한 쌍이 배를 타고 돌아오고, 이번엔 남자들만 타서 강 건너편으로 간 다음 건너편에 있는 여자 한 명만 배를 타고 돌아온다. 이때 남자들만 강 건녀편에 있고 여자들은 처음 지점에 모여있는데, 여자들만 다시 배를 타고 오면 된다.

좀 더 직관적으로 보여주면 아래와 같다. 남자를 ㄱ, ㄴ, ㄷ로 하고 각각의 아내를 A, B, C라 하자. (출발지점) - (강 건너편) 순으로 서술.

0. ㄱ ㄴ ㄷ A B C - 없음 (초기 상태)
1. ㄱ ㄴ ㄷ A - B C (B, C가 강을 건넌다)
2. ㄱ ㄴ ㄷ A B - C (B가 되돌아온다)
3. ㄱ ㄴ ㄷ - A B C (A, B가 강을 건넌다)
4. ㄱ ㄴ ㄷ C - A B (C가 돌아온다)
5. ㄷ C - ㄱ ㄴ A B (ㄱ, ㄴ이 강을 건넌다)
6. ㄴ ㄷ B C - ㄱ A (ㄴ, B가 배를 타고 되돌아온다)
7. B C - ㄱ ㄴ ㄷ A (ㄴ, ㄷ이 강을 건넌다)
8. A B C - ㄱ ㄴ ㄷ (A가 돌아온다)
9. C - ㄱ ㄴ ㄷ A B (A, B가 강을 건넌다)
10. B C - ㄱ ㄴ ㄷ A (B가 돌아온다)
11. 없음 - ㄱ ㄴ ㄷ A B C (B C가 배를 타고 강을 건넌다)

쪽배가 3명을 탈 수 있을 경우에는 안전하게 건널 수 있는 부부의 수가 5쌍으로 늘어난다. 쪽배의 용량이 4명 이상이면 안전하게 건널 수 있는 부부의 수가 무한대가 되는데, 부부 한 쌍이 계속 노를 저으면서 다른 부부들을 하나씩 옮기면 되므로 아무리 부부가 많아도 전부 건널 수 있기 때문이다.

6. 문제 4 - A와 B, 그리고 사육사[편집]

A와 B, 그리고 사육사가 각자 아이와 동물을 데리고 강을 건너려 한다. A와 B는 각각 두 명의 아이들을 데리고 있으며, 사육사는 사자 한 마리를 데리고 있다. 그런데 A와 B는 원수지간이라 강 어느편에서든지 상대가 없을 경우 상대의 아이를 해치려 하며, 사육사는 사자를 통제하느라 이를 말릴 수 없다. 사자는 사육사가 없을 경우 어디에 있든 다른 사람들을 해칠 우려가 있다.

배는 어른 아이 관계없이 두 명만 탈 수 있고, 사자의 경우도 사람 한 명으로 취급해 사육사와 같이 태울 수 있다고 가정한다. 당연하지만 사자와 아이들은 혼자 노를 저을 수 없으므로 노를 저을 수 있는 사람은 성인인 사육사, A, B 3명뿐이다. 모두가 안전하게 강을 건너려면 어떻게 해야할까?(A와 B가 같이 배를 타고 가는 것은 가능하다)

사자와 사육사는 다른 사람이 있을 경우 무조건 같이 있어야 한다. 그래서 방해만 될 것 같은 존재이지만 묘하게도 사육사와 사자가 있어야 문제를 풀 수 있다.

먼저 사육사와 사자를 배를 타고 보낸다. 그 다음 사자를 남기고 사육사만 되돌아온다. 이러면 사람이 없으므로 사자는 사육사가 없어도 아무도 해칠 수 없다. 그 다음 사육사가 A의 아이를 데리고 강을 건넌 다음. 이번에는 사자와 함께 강을 건너 돌아온다.

그 다음에는 A가 자신의 아이를 데리고 강 건너편으로 가고 혼자 되돌아온다. 다음엔 A와 B가 같이 배를 타고 가서 B만 되돌아온다. 그리고 이번이 중요한데, 이번엔 사육사와 사자가 배를 타고 간다. 이후 A가 배를 타고 돌아온 다음 A와 B가 같이 배를 타고 간다. 그리고 사육사와 사자가 배를 타고 돌아간 다음 사육사가 혼자 남은 B의 아이를 데리고 배를 타고 간다. 이번에도 사자는 자기가 있는 쪽에 사람이 없기 때문에 아무도 해칠 수 없다. 마지막으로 사육사가 사자를 데려오면 된다.

앞선 문제와 같은 방식으로 표현하면 아래와 같다. 편의상 A의 아이는 a, B의 아이는 b, 사육사와 사자는 각각 C와 c로 한다.

0. A a a B b b C c - 없음 (초기 상태)
1. A a a B b b - C c (사육사와 사자가 강을 건넌다)
2. A a a B b b C - c (사육사가 돌아온다)
3. A a B b b - C a c (사육사가 A의 아이를 데리고 건넌다)
4. A a B b b C c - a (사육사와 사자가 돌아온다)
5. B b b C c - A a a (A가 자신의 아이를 데리고 건넌다)
6. A B b b C c - a a (A가 돌아온다)
7. b b C c - A B a a (A와 B가 강을 건넌다)
8. B b b C c - A a a (B만 돌아온다)
9. B b b - A a a C c (사육사와 사자가 강을 건넌다)
10. A B b b - a a C c (A가 돌아온다)
11. b b - A a a B C c (A와 B가 강을 건넌다)
12. B b b - A a a C c (B가 돌아온다)
13. b - A a a B b C c (B가 자신의 아이를 데리고 건넌다)
14. b C c - A a a B b (사육사와 사자가 돌아온다)
15. c - A a a B b b C (사육사가 b의 아이를 데리고 강을 건넌다)
16. C c - A a a B b b (사육사가 돌아온다)
17. 없음 - A a a B b b C c (사육사가 사자를 데리고 강을 건넌다)

플래시 게임 버전에서는 엄마&아빠 및 그들의 자녀 2명씩에 경찰과 꼬마 죄수로 나와 있는데, 이 엄마&아빠가 자신의 아들딸들을 해치려 한다는 패륜적인 내용이 담겨있기도 하다. 원본은 잘 알려지지 않은 모양이며, 여기서는 임시로 A와 B로 대체했다.

7. 문제 5 - 배 옮기기[편집]

배 4척을 강 건너편으로 옮겨야 한다. 배가 강을 건너는 시간은 각각 1, 2, 8, 16이며 당연히 오래 걸리는 쪽이 큰 배다. 큰 배에는 작은 배를 하나만 넣어서 갈 수 있는데(넣은 작은 배에 다른 배를 넣는 것은 불가능하다), 배를 옮기는 시간이 최소가 되게 하려면 어떻게 해야 할까? 당연하지만 돌아올 때에도 배를 타고 돌아와야 하므로 그것도 고려해서 계산해야 한다.