늑대와 양과 배추
나룻배에 하나만 태웁니다
농부가 늑대, 양, 배추를 데리고 강을 건너려 합니다. 배가 작아 농부 외에 한 가지만 태울 수 있습니다.
농부가 자리를 비우면 늑대는 양을 잡아먹고 양은 배추를 먹어 치웁니다. 어떻게 하면 셋 모두 무사히 강 건너편으로 옮겨 놓을 수 있을까요?
이야기
농부가 늑대와 양과 배추를 데리고 강을 건너야 합니다. 배는 작아서 한 번에 하나만 실을 수 있습니다.
그런데 농부가 없으면 늑대가 양을 먹고, 양이 배추를 먹습니다. 어떻게 하면 다 무사히 건널까요?
열쇠는 다시 데려오는 것입니다. 대부분 「한 번 건넨 것을 도로 가져온다」는 생각을 못 해서 막힙니다.
양을 먼저 건넵니다(늑대와 배추는 함께 둬도 됩니다). 돌아와서 늑대를 건넵니다. 그리고 양을 다시 데리고 돌아옵니다. 양을 두고 배추를 건넵니다. 마지막으로 양을 데려옵니다.
이 문제가 오래 살아남은 까닭은 답이 어려워서가 아니라, “앞으로만 가면 된다”는 생각을 깨기 때문입니다. 때로는 물러서는 것이 나아가는 길입니다.
「상태와 옮김」으로 문제를 푸는 법의 첫걸음입니다. 지금 상태를 점으로, 할 수 있는 행동을 화살표로 그리면 길 찾기가 됩니다.
인공지능이 계획을 세우고, 로봇이 움직임을 짜고, 자동 검증 도구가 프로그램의 오류를 찾는 방식이 모두 이것입니다.
계단 넷 — 같은 사실을 네 깊이로
말을 옮겨 가며 풀어 본다
동물 인형이나 바둑돌을 강 양쪽에 놓으며 놀이하듯 옮겨 봅니다. 첫 번째에는 무조건 양을 태우고 건너가야 합니다. 그래야 남은 늑대와 배추가 평화롭습니다.
두 번째가 함정입니다. 배추를 건네주고 돌아올 때 양을 다시 태워 데리고 나오는 기발한 반전이 필요합니다. 손으로 직접 말을 옮겨 보며 길을 찾아보세요.
건너기를 세어 보세요
되돌아오는 걸음이 있어야 하기 때문입니다.
상태를 그림으로 그려 세기
이 문제를 풀려면 강 양쪽에 남겨진 안전한 상태를 분석해야 합니다. (늑대, 배추)는 안전하지만 (늑대, 양)이나 (양, 배추)는 위험합니다.
배가 오가는 과정에서 양을 다시 싣고 돌아오는 4단계가 핵심 전환점입니다. 농부-양 이동(1) → 농부 복귀(2) → 농부-늑대 이동(3) → 농부-양 복귀(4) → 농부-배추 이동(5) → 농부 복귀(6) → 농부-양 이동(7)의 최소 7단계로 완성됩니다.
되돌아오는 걸음
그래서 걸음이 거의 두 배가 됩니다.
상태 그래프의 최단 경로
이 퍼즐은 상태 공간 그래프(State-Space Graph)의 최단 경로 탐색 문제입니다. 가능한 모든 상태(강 왼쪽과 오른쪽에 누가 있는가)를 정점으로 두고, 배의 합법적 이동을 간선으로 연결합니다.
위험 상태(양과 늑대만 남음 등)를 제외하면 유효한 상태 노드는 10개뿐입니다. 시작 상태에서 목표 상태까지 너비 우선 탐색(BFS)을 적용하면 최소 이동 횟수가 7회임을 수학적으로 엄밀히 보일 수 있습니다.
그래프로 보세요
가장 짧은 길 찾기가 곧 답입니다 — 그래프 문제가 됩니다.
탐색 알고리즘
강 건너기 문제는 현대 컴퓨터 과학의 인공지능 탐색 알고리즘(A* Search), 모델 체킹(Model Checking), 오토마타 이론(Automata Theory) 및 교착 상태(Deadlock) 회피 이론의 원형입니다.
공유 자원을 안전하게 관리하면서 시스템이 안전한 상태 전이(Safe State Transition)만을 거치도록 검증하는 알고리즘은 분산 컴퓨팅 및 임베디드 제어 시스템의 핵심 원리로 적용됩니다.
선교사와 식인종
「어디서든 선교사가 식인종보다 적으면 안 된다」는 조건 때문입니다.
풀어 보기
강 건너기 퍼즐과 상태 전이. 농부(F), 늑대(W), 양(S), 배추(C)가 강 왼쪽에 있다.
(1) 첫 번째 이동에서 농부가 양(S)을 태우고 건너가야만 하는 까닭을 남겨진 대상들의 관계로 설명하시오.
(2) 전체 이동 과정에서 배가 강을 건너는 최소 횟수가 7회임을 각 단계별 이동 대상을 적어 보이시오.
(3) 4번째 이동에서 양(S)을 다시 왼쪽으로 데려오지 않으면 왜 교착 상태에 빠지거나 실패하는지 설명하시오.
(2) (1) F+S→ (2) F← (3) F+W→ (4) F+S← (5) F+C→ (6) F← (7) F+S→ 순서로 7회입니다.
답과 풀이 보기
(1) 농부가 자리를 비우면 늑대는 양을, 양은 배추를 먹습니다. 위험한 짝이 둘 다 양과 얽혀 있습니다.
늑대와 배추만 남기면 아무 일도 없으므로, 첫 걸음은 반드시 양을 데려가야 합니다.
(2) 일곱 번입니다.
① 농부+양 → ② 농부 ← ③ 농부+늑대 → ④ 농부+양 ← ⑤ 농부+배추 → ⑥ 농부 ← ⑦ 농부+양 →
(3) ④ 가 이 문제의 심장입니다. 양을 저쪽에 두고 오면 저쪽에 늑대와 양이 남습니다. 배추를 태워도 마찬가지로 저쪽에 양과 배추가 남습니다.
한 번 건넌 것을 되가져오는 것 — 앞으로만 가려는 생각을 버려야 풀립니다.
더 멀리
이 놀이는 컴퓨터가 문제를 푸는 방식 그대로입니다.
- 상태 그래프 — 가능한 상황을 점으로, 한 번의 이동을 선으로 그리면 최단 경로 문제가 됩니다
- 탐색 알고리즘 — 인공지능이 길을 찾는 기본 방식입니다
- 퍼즐 만들기 — 조건을 바꿔 자기만의 강 건너기 문제를 만들어 보세요
이어지는 장
늑대, 양, 배추가 서로를 해치지 않도록 강을 건너는 상태들을 점과 선으로 연결하는 해법은, 체스판 위의 모든 칸을 나이트가 한 번씩만 방문하는 경로 탐색 문제처럼 상태 공간 그래프를 순회하는 원리와 같습니다 — 제81장에서 논리적 제약 조건을 뚫고 나아가는 그래프 탐색의 묘미를 느껴보세요.
영감을 받은 곳
8세기 샤를마뉴 대제의 궁정 학자 알퀸(Alcuin of York)이 저술한 수학 문제집 『청소년의 지능 계발을 위한 문제들』(Propositiones ad Acuendos Juvenes) 제18번 문제에 최초로 기록되었습니다.