강 건너기
1. 개요
정해진 용량의 운송수단으로 주어진 물체, 사람 등을 옮기는 유형의 문제.
2. 상세
미니게임 등에 꽤 많이 출현하는 문제. 퀴즈치고는 게임성이 너무 좋아서 자주 사용되며, 플래시 게임 등으로 많이 접해봤을 것이다.
기본 내용은 간단하다. 강 을 사이에 두고 적게는 하나의 무리부터 많게는 서너무리들까지 반대편에 전부 옮기는 것. 그 과정까지의 바리에이션은 너무 많아서 정리하기가 좀 힘들다. 다른 두 종이 타면 한 쪽이 먹힌다든가, 배는 꼭 한명 이상이 있어야 하는 등, 원한다면 필요한 제약을 맘대로 넣으면 되는 만능 퀴즈. 노를 저을 수 있는 사람들을 제한하거나 운송수단을 여러개로 늘리는 등의 응용 문제들도 있다.
3. 문제 1 - 늑대, 양, 풀
| 무한도전 스피드 특집에도 나왔던, 가장 유명한 패턴. 늑대, 양, 풀이 있는데 한 번에 하나씩 밖에 옮길 수 없고, 사람이 없으면 늑대는 양을, 양은 풀을 먹어버린다. 모두 무사히 건너기 위해서는 어떻게 해야할까? |
[ 해답 ] 먼저 양을 싣고 건너간 뒤, 양을 내리고 혼자 돌아온다. 그리고 늑대 혹은 풀을 싣고 건너간 뒤, 양을 '''데리고 돌아오는''' 것. 그리고 양을 내려놓고 나머지 하나를 싣고 건너간 뒤, 혼자 돌아와서 다시 양을 데리고 건너가는 것이다.[랜들먼로의해답] 1.양을 가지고 간다. 2.혼자 돌아온다. 3.풀을 가지고 온다. 늑대는 그냥둔다.
4. 문제 2 - 식인종과 선교사
| 선교사와 식인종이 각각 3명씩 있으며 강을 건너려고 한다. 선교사가 식인종보다 많거나 같으면 문제가 없지만, 식인종이 선교사보다 많아지면 식인종은 선교사를 먹는다. 또한 배에는 종류를 막론하고 2명까지 탈 수 있다. 아무도 죽지 않으면서 모두 강을 건너려면 어떻게 해야 할까? |
[ 해답 ] 먼저 식인종 1명과 선교사 1명이 배를 타고 가되, 식인종을 두고 선교사만 돌아온다(식인1). 다시 식인종 2명이 배를 타고 가서, 식인종을 두고 식인종이 돌아온다(식인2). 이번에는 '''선교사 2명이 배를 타고 가서, 선교사가 1명만 내리고 식인종과 함께 돌아온다(식인1, 선교1).''' 이후 선교사 2명이 가서 모두 내린다(식인1, 선교3). 이후엔 먼저 가 있던 식인종 혼자서 남은 식인종을 1명씩 데려오면 끝.
이 문제의 핵심은 '''아무 문제 없이 이동할 수 있는 조건을 찾는 것'''이다. 즉, 다른 요소에 영향을 주지 않는 요소를 찾는 것. 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와 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 (사육사가 사자를 데리고 강을 건넌다)
알려진 문제에서는 A와 B가 각각 엄마 아빠이며 자신의 딸과 아들을 해치려 한다는 패륜적인 내용이 담겨있기도 하다. 원본은 잘 알려지지 않은 모양이며 임시로 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을 타고 돌아오는 것도 동일하다.