강 건너기 문제

,

,

,

,

,

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

[ 해답 ]

||<tablebordercolor=#552582>먼저 양을 싣고 건너간 뒤, 양을 내리고 혼자 돌아온다. 그리고 늑대 혹은 풀을 싣고 건너간 뒤, 양을 데리고 돌아오는 것. 그리고 양을 내려놓고 나머지 하나를 싣고 건너간 뒤, 혼자 돌아와서 다시 양을 데리고 건너가는 것이다.||

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

[ 해답 ]

||<tablebordercolor=#552582>먼저 식인종 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. C M M M - C C (식인종 2명이 강을 건넌다)
2. C C M M M - C (식인종 1명만 되돌아온다)
이하 동일.

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

쪽배의 정원이 노 젓는 사람 포함 3명인 경우에는 선교사와 식인종의 수가 같다는 전제 하에서는 안전하게 건널 수 있는 선교사와 식인종의 수가 각 5명으로 늘어난다. 쪽배의 정원이 3명이고 선교사가 식인종보다 1명이라도 더 많다면 선교사 1명이 계속 노를 저으면서 다른 선교사와 식인종을 1명씩 태워서 옮기면 되므로 안전하게 건널 수 있는 선교사와 식인종의 수는 무한대가 된다. 쪽배의 정원이 4명 이상이면 선교사와 식인종 한 쌍이 계속 노를 저으면서 다른 식인종과 선겨사 한 쌍을 계속 태워 옮기면 되므로 선교사와 식인종의 수가 같더라도 안전하게 건널 수 있는 선교사와 식인종의 수는 무한대가 된다.||

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

[ 해답 ]

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

좀 더 직관적으로 보여주면 아래와 같다. 남자를 ㄱ, ㄴ, ㄷ로 하고 각각의 아내를 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명 이상이면 안전하게 건널 수 있는 부부의 수가 무한대가 되는데, 부부 한 쌍이 계속 노를 저으면서 다른 부부들을 하나씩 옮기면 되므로 아무리 부부가 많아도 전부 건널 수 있기 때문이다.

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

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

[ 해답 ]

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

먼저 사육사와 사자를 배를 타고 보낸다. 그 다음 사자를 남기고 사육사만 되돌아온다. 이러면 사람이 없으므로 사자는 사육사가 없어도 아무도 해칠 수 없다. 그 다음 사육사가 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로 대체했다.

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

[ 해답 ]

||<tablebordercolor=#552582>돌아올 때까지 고려하면 배가 총 이동해야하는 횟수는 5회이다. 갈 때에는 다 한번씩은 옮겨야 하기 때문에 최소 16을 한번 옮기는 것은 감수해야 한다. 돌아올 때에는 최대한 1과 2의 배를 타서 시간을 절약하는 것이 키포인트.

1. 2에 1을 태워서 옮긴다(2시간).
2. 1을 타고 돌아온다(1시간).
3. 8을 16에 태워서 간다(16시간).
4. 2를 타고 돌아온다(2시간).
5, 2에 1을 태워서 옮긴다(2시간).

이렇게 하면 8을 타고 돌아오는 일 없이 최소 시간이 되며, 총 시간은 23시간이다. (실제로는 배에서 내린 후 정박시키고 다른 배를 타는 데 시간이 더 걸리지만 여기서는 중요한 내용이 아니므로 무시한다.) 물론 2번과 4번의 순서를 뒤바꿔서 처음에 2를 타고 돌아오고 두번째에는 1을 타고 돌아오는 것도 동일하다.

||<tablebordercolor=#8258fa>성겸 엔터프라이즈의 패미컴 게임 <Olympic I.Q.>에 나온 문제이다. 조련사가 코끼리, 호랑이, 개, 고양이, 쥐를 모두 데리고 강을 건너려 한다. 배가 작아서 모든 동물을 한꺼번에 배에 태울 수 없으므로 나눠서 태워야 하는데, 코끼리는 쥐를 제외하고는 다른 동물과 함께 태울 수 없고 호랑이는 개와 함께 태울 경우 다른 동물을 더 태울 수 없다. 또한 10쌍 중 코끼리-호랑이, 호랑이-개, 개-고양이, 고양이-쥐, 쥐-코끼리 이렇게 5쌍은 조련사가 없으면 서로 싸운다. 어떻게 하면 최소한의 이동으로 5마리의 동물을 안전하게 강 건너편으로 옮길 수 있을까? ||

[ 해답 ]

||<tablebordercolor=#552582>먼저 호랑이와 고양이와 쥐를 태우고 강을 건넌다. 그런 다음 호랑이와 고양이는 내리고 쥐만 태우고 되돌아와서, 쥐는 배애 놓고 코끼리를 태워서 강을 건넌다. 거기서 또 코끼리는 내리고 호랑이를 쥐와 함께 태우고 되돌아와서, 호랑이와 쥐는 내리고 개만 태우고 강을 건넌다. 그런 다음 개는 내리고 고양이를 태우고 되돌아온 뒤, 호랑이와 쥐를 고양이와 함께 태우고 강을 건너면 끝.

0. 코끼리 호랑이 개 고양이 쥐 - 없음 (초기 상태)
1. 코끼리 개 - 호랑이 고양이 쥐 (호랑이와 고양이와 쥐를 태우고 강을 건넌다.)
2. 코끼리 개 쥐 - 호랑이 고양이 (쥐를 태우고 돌아온다.)
3. 개 - 코끼리 호랑이 고양이 쥐 (코끼리와 쥐를 태우고 강을 건넌다.)
4. 호랑이 개 쥐 - 코끼리 고양이 (호랑이와 쥐를 태우고 돌아온다.)
5. 호랑이 쥐 - 코끼리 개 고양이 (개를 태우고 강을 건넌다.)
6. 호랑이 고양이 쥐 - 코끼리 개 (고양이를 태우고 돌아온다.)
7. 없음 - 코끼리 호랑이 개 고양이 쥐 (호랑이와 고양이와 쥐를 태우고 강을 건넌다.)

Olympic I.Q.에서는 동물의 중량을 코끼리=4800, 호랑이=3700, 개=1200, 고양이=600, 쥐=200으로 설정했으며 태울 수 있는 중량 합계를 5000으로 설정했다.(단, 조련사의 몸무게는 중량 계산에서 제외한다.) 이 계산에 의거하여 각 이동에 대해 중량 합계를 계산하면 1번째와 7번째(호랑이+고양이+쥐)는 4500, 2번째(쥐)는 200, 3번째(코끼리+쥐)는 5000, 4번째(호랑이+쥐)는 3900, 5번째(개)는 1200, 6번째(고양이)는 600이다.

만약 배의 허용 중량이 6000으로 늘어날 경우 1번째는 코끼리를 제외한 모든 동물을 옮기고(중량합계 5700), 2번째는 개와 쥐만 되돌아오고(중량합계 1400), 3번째는 코끼리와 개를 옮기고(중량합계 6000), 4번째는 호랑이와 고양이가 되돌아오고(중량합계 4300), 5번째는 호랑이+고양이와 함께 쥐까지 같이 옮기면(중량합계 4500) 끝나므로 최소 이동 횟수가 5회로 줄어든다. 배의 허용 중량이 6200 이상이면 최소 이동 횟수가 3회로 줄어들고, 10500 이상이면 이런 복잡한 과정 없이 모든 동물을 한꺼번에 다 옮길 수 있다.||