농부의 강 건너기 시뮬레이터

준비 단계: 탐색이란 무엇인가?

미로를 풀거나 퍼즐을 맞출 때 우리는 「이쪽으로 가면 막히려나? 저쪽으로 가면 목표가 나올까?」 하며 여러 경우를 머릿속으로 비교해 봅니다. 인공지능도 마찬가지입니다.

💡 탐색(Search)이란?

현재 상태(State)에서 목표 상태에 이르는 경로를 찾기 위해 가능한 경우를 체계적으로 살펴보는 과정. 상태·연산자·목표라는 세 요소로 문제를 상태 공간(State Space)으로 모델링한 뒤 탐색합니다.

상태 (State)

농부·늑대·양·양배추가 각각 왼쪽 또는 오른쪽에 있는 현재 배치

연산자 (Operator)

농부가 혼자 또는 한 가지와 함께 반대편으로 건너는 행동 (최대 4가지)

목표 (Goal)

농부·늑대·양·양배추 모두 오른쪽에 있는 상태 (오, 오, 오, 오)

1단계: 문제 규칙 알아보기

농부는 늑대🐺, 양🐑, 양배추🥬를 왼쪽에서 오른쪽 강가로 모두 옮겨야 합니다.
배에는 농부👨‍🌾와 한 가지만 탈 수 있습니다.

1. 배의 용량

배에는 농부 + 1가지만 탑승 가능. 농부 없이 배는 움직이지 않습니다.

2. 금지 조합

농부가 없는 쪽에
늑대🐺 + 양🐑 → 늑대가 양을 먹음
양🐑 + 양배추🥬 → 양이 양배추를 먹음

3. 목표와 최소 해

전원을 오른쪽으로 옮기면 성공. 최소 7번의 건너기로 해결 가능합니다.

상태 공간 모델

구성 요소	설명
상태 표현	`(농부, 늑대, 양, 양배추)` — 각 요소는 왼 또는 오
초기 상태	`(왼, 왼, 왼, 왼)` — 모두 왼쪽
목표 상태	`(오, 오, 오, 오)` — 모두 오른쪽
전체 상태 수	2⁴ = 16개, 그중 유효 상태 10개
연산자	농부가 혼자 / 늑대와 / 양과 / 양배추와 건넌다 (같은 쪽에 있어야 탑승 가능)
최적 해	7번 건너기

2단계: 직접 해 보기

건넌 횟수: 0 / 목표: 7번 이내

왼쪽 강가

오른쪽 강가

강가의 대상을 탭해서 배에 태우세요. 농부는 배에 항상 탑니다.

조작 방법

농부와 같은 쪽 강가의 대상(늑대/양/양배추)을 탭해서 선택
선택하지 않으면 농부만 혼자 건넙니다
[건너기] 버튼으로 이동. 규칙 위반 시 이유를 알려드립니다.

💡 7번 이내에 성공하면 최적 해를 찾은 것입니다.

단계: 0 / 7

왼쪽 강가

오른쪽 강가

버튼을 눌러 AI 풀이를 시작하세요

BFS 탐색 원리

너비 우선 탐색(BFS): 거리가 같은 상태를 먼저 모두 확인
방문한 상태는 다시 탐색하지 않아 무한 루프를 방지
모든 이동의 비용이 같으므로 BFS가 최단 경로를 보장합니다 → 7수 해

BFS가 탐색하며 만드는 상태 공간 트리입니다. 상태 하나가 노드(Node) 하나입니다.
붉은 노드 = 규칙 위반(가지치기), 회색 노드 = 이미 발견(큐에 넣은 적 있음), 흰 노드 = 탐색했지만 정답 경로가 아닌 상태, 노란 노드 = 정답 경로, 초록 노드 = 목표

총 유효 상태 10개 중 BFS가 탐색하는 경로: 최단 7수

3단계: 핵심 원리 및 코드

강 건너기의 상태를 튜플로 표현하면 BFS 탐색 코드가 매우 간결해집니다. 각 위치를 0(왼쪽)과 1(오른쪽)으로 나타내면 (농부, 늑대, 양, 양배추) 형태의 정수 튜플이 됩니다.

왜 튜플인가? 튜플은 만든 뒤 바꿀 수 없어서 집합(set)에 넣을 수 있고, 그래서 방문 여부를 O(1)에 확인할 수 있습니다. BFS는 이 성질 덕분에 이미 본 상태를 빠르게 걸러 냅니다.

Python (의사코드)

from collections import deque

# 상태: (농부, 늑대, 양, 양배추)  0=왼쪽, 1=오른쪽
INITIAL = (0, 0, 0, 0)
GOAL    = (1, 1, 1, 1)

def is_safe(state):
    farmer, wolf, sheep, cabbage = state
    # 농부 없는 쪽에 늑대·양이 같이 있으면 위험
    if wolf == sheep and farmer != wolf:
        return False
    # 농부 없는 쪽에 양·양배추가 같이 있으면 위험
    if sheep == cabbage and farmer != sheep:
        return False
    return True

def bfs():
    queue   = deque([(INITIAL, [])])   # (현재 상태, 경로)
    visited = {INITIAL}

    while queue:
        state, path = queue.popleft()

        if state == GOAL:
            return path  # 최단 경로 반환

        farmer = state[0]
        # 연산자: 농부가 혼자 / 늑대와 / 양과 / 양배추와 건넌다
        for cargo in [None, 1, 2, 3]:   # None=혼자, 1=늑대, 2=양, 3=양배추
            # 데려갈 대상이 농부와 같은 쪽에 있어야 한다
            if cargo is not None and state[cargo] != farmer:
                continue

            new = list(state)
            new[0] = 1 - farmer          # 농부 이동
            if cargo is not None:
                new[cargo] = new[0]      # 화물도 함께 이동

            new_state = tuple(new)
            if new_state not in visited and is_safe(new_state):
                visited.add(new_state)
                queue.append((new_state, path + [(state, new_state)]))

    return None   # 해 없음 (이 문제에선 발생하지 않음)

solution = bfs()
print(f"최단 해: {len(solution)}번 건너기")  # → 7번

상태를 튜플로 표현하는 이유

같은 상태인지 ==로 바로 비교 가능
set·dict에 넣어 방문 여부 O(1) 확인
불변(immutable)이라 실수로 덮어쓸 위험 없음

가지치기 조건

농부가 없는 쪽에 늑대+양 → 제거
농부가 없는 쪽에 양+양배추 → 제거
이미 발견한(큐에 넣은 적 있는) 상태 → 큐에 넣지 않음

4단계: 오해와 진실

흔한 오해

「목표(오른쪽)에서 멀어지는 이동은 손해 아닌가요? 4번째 수에서 양을 다시 왼쪽으로 데려오는 건 퇴보 아닌가요?」

올바른 개념

아닙니다. 이 이동은 반드시 필요합니다.

늑대와 양배추는 둘만 남겨도 안전하지만, 양은 늑대와도 양배추와도 함께 둘 수 없습니다. ③번 수를 마치면 오른쪽에 늑대와 양이 함께 있으므로, 농부가 그냥 돌아오면 규칙 위반입니다. 그래서 양을 다시 왼쪽으로 데려와야만 늑대·양배추를 안전하게 나를 수 있습니다. 너비 우선 탐색은 이런 「목표에서 일시적으로 멀어지는 경로」도 버리지 않고 함께 탐색하기 때문에 이 해를 놓치지 않습니다.

핵심: 4번째 수 — 양을 왼쪽으로 다시 데려온다

수	행동	왼쪽	오른쪽
초기	—	👨‍🌾 🐺 🐑 🥬	—
①	양과 함께 →	🐺 🥬	👨‍🌾 🐑
②	혼자 돌아옴 ←	👨‍🌾 🐺 🥬	🐑
③	늑대와 함께 →	🥬	👨‍🌾 🐺 🐑
④ ★	양을 데리고 돌아옴 ←	👨‍🌾 🐑 🥬	🐺
⑤	양배추와 함께 →	🐑	👨‍🌾 🐺 🥬
⑥	혼자 돌아옴 ←	👨‍🌾 🐑	🐺 🥬
⑦	양과 함께 →	—	👨‍🌾 🐺 🐑 🥬

④번 수에서 양을 다시 왼쪽으로 가져오지 않으면, 오른쪽에 농부 없이 남은 늑대와 양이 함께 있어 규칙 위반이 됩니다. 목표에서 잠시 멀어지는 이 이동이 없으면 문제를 풀 수 없습니다.