하노이의 탑 시뮬레이터

준비 단계: 탐색과 상태 공간

하노이의 탑은 단순해 보이지만, 원판 수가 늘어날수록 가능한 상태 수가 폭발적으로 증가합니다. 인공지능은 이 광대한 상태 공간을 체계적으로 탐색해 해를 찾습니다. 다만 하노이의 탑처럼 규칙에서 최적 해를 곧바로 만들어 내는 방법이 알려진 문제라면, 상태 공간을 탐색하지 않고 그 방법을 쓰는 편이 훨씬 빠릅니다. 「AI 자동 풀이」 탭이 그 방법을 씁니다.

💡 상태 공간이란?

문제에서 나타날 수 있는 모든 상태(State)의 집합입니다. 하노이 n=3일 때 상태는 3³ = 27가지이며, 초기 상태에서 목표 상태까지의 경로가 곧 「풀이」입니다. 연산자(이동)를 적용해 한 상태에서 다른 상태로 이동하며 탐색이 진행됩니다.

상태 (State)

각 원판이 어느 기둥(A·B·C)에 있는지를 나타내는 배치. n=3이면 (A,A,A) 형태

연산자 (Operator)

한 기둥의 맨 위 원판 하나를 다른 기둥의 맨 위로 옮긴다. 단, 큰 원판이 작은 원판 위에 올 수 없음

목표 (Goal)

모든 원판이 A기둥에서 C기둥으로 이동한 상태. n=3이면 (C,C,C)

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

기둥 A에 쌓인 원판을 기둥 C로 모두 옮기면 성공입니다.
기둥 B는 보조 기둥으로 사용할 수 있습니다.

1. 한 번에 한 장

한 번에 맨 위 원판 하나만 집어서 다른 기둥으로 옮길 수 있습니다.

2. 순서 규칙

큰 원판이 작은 원판 위에 올 수 없습니다. 항상 작은 것이 위에 있어야 합니다.

3. 최소 이동

n개 원판의 최소 이동 횟수는 2ⁿ − 1번. n=3이면 7번.

상태 공간 모델

구성 요소	설명
상태 표현	작은 원판부터 순서대로 어느 기둥에 있는지. n=3이면 `(원판1, 원판2, 원판3)` 각각 A·B·C
초기 상태	`(A, A, A)` — 모두 A기둥 (가장 큰 원판이 맨 아래)
목표 상태	`(C, C, C)` — 모두 C기둥으로 이동
상태 공간 크기	3ⁿ (n=3이면 27개)
연산자 조건	출발 기둥에 원판이 있어야 하고, 도착 기둥의 맨 위보다 작아야 함
최소 이동 횟수	2ⁿ − 1 (n=3이면 7번)

2단계: 직접 해 보기

원판 수:

이동: 0 /최소: 7

기둥을 탭해 원판을 집고, 다른 기둥을 탭해 놓으세요

조작 방법

기둥을 탭하면 맨 위 원판을 집습니다 (기둥 하이라이트)
다른 기둥을 탭하면 원판을 내려놓습니다
같은 기둥 다시 탭 → 선택 취소
규칙 위반(큰 원판 → 작은 원판 위)이면 이유를 알려드립니다

💡 최소 이동 횟수 2ⁿ − 1번으로 성공하면 최적 해입니다.

원판 수:

단계: 0 / 7

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

속도:

재귀 분할 원리

n개를 C로 옮기려면: n-1개를 B로 → 큰 원판을 C로 → n-1개를 B에서 C로
재귀 호출이 반복되며 최적 이동 수열을 생성
총 2ⁿ − 1번의 이동으로 완료 보장

3단계: 핵심 원리 및 코드

하노이의 탑은 재귀(Recursion)로 표현하면 매우 간결합니다. 단, 연산자를 적용하려면 반드시 조건(전제)이 충족되어야 합니다 — 이것이 단순 반복과 다른 점이자, 탐색 문제의 핵심입니다.

연산자에 붙는 조건(전제):
원판을 기둥 X → 기둥 Y로 이동하려면, ① X의 맨 위에 원판이 있어야 하고, ② Y의 맨 위 원판보다 작아야 합니다. 이 조건이 없으면 연산자를 적용할 수 없습니다. 탐색에서는 이 조건을 검사해 유효한 이동만 후보로 넣습니다.

Python (재귀 의사코드)

def hanoi(n, src, aux, dst, moves=[]):
    """
    n   : 이동할 원판 수
    src : 출발 기둥 ('A', 'B', 'C')
    aux : 보조 기둥
    dst : 목표 기둥
    """
    if n == 0:
        return  # 기저 사례: 원판 0개 → 아무것도 안 함

    # ① 위의 n-1개를 보조 기둥으로 옮긴다  (연산자 조건 자동 충족)
    hanoi(n - 1, src, dst, aux, moves)

    # ② 가장 큰 원판을 목표 기둥으로 옮긴다
    #    조건 전제: dst 맨 위가 비어 있거나 더 큰 원판임 → 항상 보장됨
    moves.append((src, dst))

    # ③ 보조 기둥의 n-1개를 목표 기둥으로 옮긴다
    hanoi(n - 1, aux, src, dst, moves)

    return moves

solution = hanoi(3, 'A', 'B', 'C')
print(f"총 이동 횟수: {len(solution)}")  # → 7
# solution = [('A','C'), ('A','B'), ('C','B'), ('A','C'), ('B','A'), ('B','C'), ('A','C')]

재귀 호출 구조

문제를 같은 형태의 더 작은 문제로 분해
기저 사례(n=0)에서 재귀가 멈춤
이동을 만드는 호출(n ≥ 1) 횟수 = 이동 횟수 = 2ⁿ − 1

연산자 조건(전제)

빈 기둥에서 원판 집기 → 불가
더 큰 원판을 위에 올리기 → 불가
재귀 해법은 이 조건을 항상 자동 충족

4단계: 오해와 진실

흔한 오해

「원판이 한 개 늘어 봤자 조금 더 어려운 거 아닌가요?
원판 10개도 적당히 시간을 들이면 풀 수 있지 않을까요?」

올바른 개념

전혀 그렇지 않습니다. 기하급수적 증가입니다.

원판 수 n이 하나 늘 때마다 상태 수는 3배, 최소 이동 횟수는 2배 + 1이 됩니다. n=20이 되면 최소 이동 횟수가 백만을 훌쩍 넘어, 1초에 한 번씩 옮겨도 약 12일이 걸립니다.

원판 수에 따른 복잡도

원판 수 (n)	상태 수 (3ⁿ)	최소 이동 (2ⁿ−1)	1초 1번 기준 소요 시간
3	27	7	7초
5	243	31	31초
10	59,049	1,023	약 17분
20	3,486,784,401	1,048,575	약 12일

n=64(하노이 전설의 원판 수)에서 최소 이동 횟수는 약 1.8 × 10¹⁹번 — 1초에 10억 번 옮겨도 약 585년이 걸립니다.