→늑대, 염소, 양배추 실험실

9세기 문제집에서 1,200년을 살아남은, 강 건너기 퍼즐

늑대, 염소, 양배추를 강 건너로 옮겨야 합니다. 배에는 나와 하나만 탈 수 있어요. 내가 없는 곳에서 늑대는 염소를, 염소는 양배추를 먹습니다. 셋 다 무사히 건널 수 있을까요?

건너는 문제는 배가 아니라 상태의 지도가 푼다.

Experiment

직접 만져보기

건넌 횟수 0태울 것을 하나 탭해 고르고(안 골라도 돼요), 건너기를 누르세요.

이쪽 기슭

🧑‍🌾

⛵≈

건너편

📖 더 읽기 — 왜 필요한가 · 인사이트 · 흔한 오해 · 수식 정리펼치기 ▾

Why

왜 필요한가

이 퍼즐은 9세기의 라틴어 문제집에 실려 있습니다. 두뇌를 단련하려는 젊은이들을 위한 책이었어요. 1,200년이 지난 지금도 전 세계 교실에서 그대로 풀리고 있습니다.

이 문제가 그렇게 오래 살아남은 이유는 답이 아니라 눈에 있습니다. '누가 어느 기슭에 있는가'라는 상태로 문제를 표현하는 순간, 막막한 퍼즐이 지도 위의 길찾기로 변해요.

그 눈이 바로 상태 공간 탐색입니다. 내비게이션이 길을 찾고, AI가 계획을 세우고, 컴퓨터가 퍼즐을 푸는 방법의 원형이 이 작은 강가에 있어요.

Insight

영상에서 말한 인사이트

“배를 조종하지 말고, 상태를 조종하라.”
게임에서 누른 버튼은 '건너기'지만, 실제로 바꾼 것은 상태입니다. 문제를 상태로 표현하는 순간 전체가 한 장의 지도에 들어와요. 열 개의 점이면 이 퍼즐의 전부입니다.

“모든 길은 염소 되돌리기를 지난다.”
상태 지도에는 지름길이 없습니다. 어느 길로 가도 한 번 건넨 염소를 도로 데려오는 수를 지나요. 후퇴처럼 보이는 수가 사실은 전진이라는 것을 지도가 증명합니다.

Misconception

사람들이 흔히 하는 오해

앞으로만 부지런히 옮기는 것이 가장 빠른 길이다.

✓

이 퍼즐은 되돌아가는 수 없이는 절대 풀리지 않습니다. 상태 지도를 펼치면 출발에서 도착으로 가는 모든 길이 '염소 되돌리기'를 지나요. 뒤로 가는 한 수가 낭비가 아니라 유일한 길입니다.

퍼즐마다 번뜩이는 아이디어가 따로 필요하다.

✓

상태와 이동만 그리면 어떤 퍼즐이든 같은 방법으로 풀립니다. 가능한 상태를 점으로, 이동을 선으로 그리고 길을 찾는 것이에요. 컴퓨터가 미로, 큐브, 내비게이션을 푸는 방식이 전부 이것입니다.

Formula

수식으로 정리하기

강가에서 몸으로 겪은 것을 수학의 언어로 쓰면 이렇습니다. 문제를 상태로 표현하고, 풀이를 상태 사이의 길로 바꾸는 것이에요.

🔬 공식 해부 — 게임에서 겪은 것과 짝지어 보기

+ =

상태

문제의 한 장면을 정보 한 묶음으로 요약합니다. 모양도 색도 필요 없고, 누가 어디 있는지만 남겨요.

상태의 개수

네 주인공이 각각 두 기슭 중 하나에 있으니 배치는 최대 16가지입니다. 잡아먹히는 배치를 빼면 안전한 상태는 10개뿐이에요.

풀이 = 경로

퍼즐의 정답은 상태 지도 위의 길입니다. 최소 7번이라는 답도 '가장 짧은 길의 길이'라는 뜻이에요.

In Real Life

현실에서 만나는 곳

퍼즐과 게임

루빅스 큐브의 상태는 약 4,300경 가지지만, 상태의 지도라는 사실은 같습니다. 어떤 상태든 20수 안에 풀린다는 것이 증명되어 있어요.

AI의 계획

로봇 청소기의 동선, 게임 AI의 수읽기, 물류 창고의 경로 계획까지. AI가 '계획'이라 부르는 일의 뼈대가 상태 공간 탐색입니다.

기계의 상태 설계

엘리베이터, 세탁기 코스, 신호등은 모두 상태와 이동으로 설계된 기계입니다. 프로그래머는 이런 설계도를 상태 기계라고 불러요.

Practice

풀어보기 — 유형 정복

✏️ 유형별 문제 4개 — 스스로 풀어 정복하기탭해서 문제 풀기 ▾

정복 0 / 4

늑대, 염소, 양배추를 모두 무사히 건네는 데 필요한 최소 건너기 횟수는 몇 번일까요?

번

첫 수로 반드시 염소를 건네야 하는 이유는 무엇일까요?

네 주인공(농부, 늑대, 염소, 양배추)이 각각 두 기슭 중 한쪽에 있을 때, 배치는 최대 몇 가지일까요?

상태 지도가 '염소 되돌리기'에 대해 증명해 주는 사실은 무엇일까요?

Watch

개념은 이어진다

이전 개념

deg

쾨니히스베르크의 다리

지도를 점과 선으로 바꾼 오일러의 눈 — 이번엔 상태를 점과 선으로 바꾼다.

← 쾨니히스베르크의 다리 실험실

다음 개념으로 연결

nCr

경우의 수

2×2×2×2처럼 상태를 '세는' 문법 — 지도가 커지기 전에 크기를 가늠하는 기술.

경우의 수 실험실로 이동 →