하노이의 탑을 푸는 프로그램을 Python과 C 언어로 써 봐요. 모두 원판 3개를 왼쪽 기둥에서 오른쪽 기둥으로 옮기는 순서를 출력해요. 생각하는 방식은 하노이의 탑 알고리즘에서 설명했으니, 여기서는 코드와 실행하는 법을 중심으로 소개해요.
Python에서 재귀로 풀기
가장 기본적인 형태예요. “위의 n−1개를 치운다 → 원판 n을 움직인다 → n−1개를 되돌린다”를 그대로 함수로 만들어요.
def hanoi(n, src, dst, via, moves):
if n == 0:
return
hanoi(n - 1, src, via, dst, moves) # 위의 n-1개를 치운다
moves.append((n, src, dst)) # 원판 n을 움직인다
hanoi(n - 1, via, dst, src, moves) # n-1개를 되돌린다
moves = []
hanoi(3, "왼쪽", "오른쪽", "가운데", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
print(f"{i}번째 수: 원판 {disc}, {src} → {dst}")
print(f"모두 {len(moves)}수") hanoi.py라는 이름으로 저장하고 python3 hanoi.py로 실행하면 다음과 같이 출력돼요.
1번째 수: 원판 1, 왼쪽 → 오른쪽
2번째 수: 원판 2, 왼쪽 → 가운데
3번째 수: 원판 1, 오른쪽 → 가운데
4번째 수: 원판 3, 왼쪽 → 오른쪽
5번째 수: 원판 1, 가운데 → 왼쪽
6번째 수: 원판 2, 가운데 → 오른쪽
7번째 수: 원판 1, 왼쪽 → 오른쪽
모두 7수 hanoi(3, ...)의 3을 바꾸면 몇 개든 풀 수 있어요. 다만 수는 2ⁿ−1번이라서 원판 20개면 약 100만 수, 30개면 약 10억 수로 금세 어마어마해져요. Python은 재귀 깊이에 상한(기본 1000단쯤)이 있지만, 하노이의 탑의 재귀 깊이는 원판 개수+1단이라서 문제가 되기 전에 수가 너무 많아져요.
Python에서 재귀 없이 풀기
손으로 풀 때의 순서(푸는 법 기사의 두 가지 규칙)를 그대로 반복으로 쓰는 형태예요. 기둥은 0(왼쪽)·1(가운데)·2(오른쪽) 번호로 다뤄요.
def hanoi_loop(n):
names = ["왼쪽", "가운데", "오른쪽"]
pegs = [list(range(n, 0, -1)), [], []] # 아래에서 위로
order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2] # 1이 도는 순서
pos = 0 # 1이 있는 기둥(order의 몇 번째인지)
moves = []
for m in range(1, 2 ** n):
if m % 2 == 1:
# 홀수 번째: 1을 정한 방향으로 옆 기둥으로
a = order[pos]
pos = (pos + 1) % 3
b = order[pos]
else:
# 짝수 번째: 1이 놓이지 않은 두 기둥에서 작은 쪽을 큰 쪽으로
a, b = [p for p in range(3) if p != order[pos]]
if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
a, b = b, a
pegs[b].append(pegs[a].pop())
moves.append((pegs[b][-1], names[a], names[b]))
return moves
for i, (disc, src, dst) in enumerate(hanoi_loop(3), 1):
print(f"{i}번째 수: 원판 {disc}, {src} → {dst}") 출력은 재귀 형태와 완전히 같은 7수가 돼요. 원판 1~10개 어느 경우든 재귀 형태와 같은 순서가 나오는 것을 확인했어요.
Python에서 이진수로 바로 구하기
m번째 수에서 무엇을 할지를 그때까지의 수를 따라가지 않고 계산하는 형태예요. 식의 의미는 알고리즘 기사에서 설명해요.
def hanoi_bits(n):
for m in range(1, 2 ** n):
disc = (m & -m).bit_length() # 끝의 0의 개수+1
src = (m & (m - 1)) % 3
dst = ((m | (m - 1)) + 1) % 3
yield disc, src, dst
print(list(hanoi_bits(3))) 실행하면 [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]이라고 나와요. (원판, 출발 기둥, 도착 기둥)의 묶음으로, 위의 7수와 같아요. 이 식은 원판이 홀수 개면 기둥 0에서 기둥 2로, 짝수 개면 기둥 0에서 기둥 1로 옮기는 순서를 내므로, 짝수 개를 오른쪽으로 옮기고 싶을 때는 기둥 1과 기둥 2를 바꿔서 써요.
C 언어에서 재귀로 풀기
C 언어에서도 형태는 Python과 같아요.
#include <stdio.h>
static int count = 0;
void hanoi(int n, const char *src, const char *dst, const char *via) {
if (n == 0) return;
hanoi(n - 1, src, via, dst);
count++;
printf("%d번째 수: 원판 %d, %s → %s\n", count, n, src, dst);
hanoi(n - 1, via, dst, src);
}
int main(void) {
hanoi(3, "왼쪽", "오른쪽", "가운데");
printf("모두 %d수\n", count);
return 0;
} hanoi.c라는 이름으로 저장하고 cc -o hanoi hanoi.c로 컴파일해서 ./hanoi로 실행하면, Python 재귀 형태와 같은 7수와 “모두 7수”가 출력돼요. 문자열에 한국어를 쓰고 있으니 파일은 UTF-8로 저장해 주세요.
쓸 때 막히기 쉬운 부분
- 인수의 순서를 헷갈린다: 첫 번째 호출은 “쓰는 기둥”과 “옮길 곳”을 바꾸고, 두 번째는 “옮길 곳의 출발”과 “쓰는 기둥”을 바꿔요. 여기를 틀리면 규칙을 어기는 수가 나와요.
- 멈추는 조건을 잊는다:
n == 0(또는n == 1)에서 멈추지 않으면 끝없이 호출을 계속해요. - 확인하는 법: 나온 순서를 판에 맞춰 보고, 큰 원판을 작은 원판 위에 놓는 수가 없는지, 수가 2ⁿ−1번인지 확인하면 안심이에요.
