강 건너기 문제
덤프버전 :
분류
1. 개요[편집]
정해진 용량의 운송수단으로 주어진 물체, 사람 등을 옮기는 유형의 문제.
2. 상세[편집]
미니게임 등에 꽤 많이 출현하는 문제. 퀴즈치고는 게임성이 너무 좋아서 자주 사용되며, 줌비니 시리즈, 레이튼 교수 시리즈나 플래시 게임 등으로 많이 접해봤을 것이다.
기본 내용은 간단하다. 강을 사이에 두고 정해진 숫자의 무리를 반대편에 전부 옮기는 것. 그 과정까지의 바리에이션은 너무 많아서 정리하기가 좀 힘들다. 다른 두 종이 타면 한 쪽이 먹힌다든가, 배는 꼭 한명 이상이 있어야 하는 등, 원한다면 필요한 제약을 맘대로 넣으면 되는 만능 퀴즈. 노를 저을 수 있는 사람들을 제한하거나 운송수단을 여러개로 늘리는 등의 응용 문제들도 있다.
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번 사례에서는 '식인종과 선교사가 함께 이동해야' 양쪽의 머릿수가 같아진다는 점이 핵심.
쪽배의 정원이 노 젓는 사람 포함 3명인 경우에는 선교사와 식인종의 수가 같다는 전제 하에서는 안전하게 건널 수 있는 선교사와 식인종의 수가 각 5명으로 늘어난다. 쪽배의 정원이 3명이고 선교사가 식인종보다 1명이라도 더 많다면 선교사 1명이 계속 노를 저으면서 다른 선교사와 식인종을 1명씩 태워서 옮기면 되므로 안전하게 건널 수 있는 선교사와 식인종의 수는 무한대가 된다. 쪽배의 정원이 4명 이상이면 선교사와 식인종의 수가 같더라도 안전하게 건널 수 있는 선교사와 식인종의 수는 무한대가 된다.
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이며 당연히 오래 걸리는 쪽이 큰 배다. 큰 배에는 작은 배를 하나만 넣어서 갈 수 있는데(넣은 작은 배에 다른 배를 넣는 것은 불가능하다), 배를 옮기는 시간이 최소가 되게 하려면 어떻게 해야 할까? 당연하지만 돌아올 때에도 배를 타고 돌아와야 하므로 그것도 고려해서 계산해야 한다. |
[ 해답 ] 돌아올 때까지 고려하면 배가 총 이동해야하는 횟수는 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을 타고 돌아오는 것도 동일하다.
이 문서의 내용 중 전체 또는 일부는 문서의 r131 판{{{#!wiki style="display: inline; display: 2.2;"
, 2.2번 문단}}}에서 가져왔습니다. 이전 역사 보러 가기
이 문서의 내용 중 전체 또는 일부는 2023-11-10 01:27:07에 나무위키 강 건너기 문제 문서에서 가져왔습니다.