Page 178 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

05-3 하노이의 탑

여기에서는 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘인 ‘하노이의 탑’에 대해
살펴보겠습니다.

하노이의 탑
하노이의 탑(Towers of Hanoi)은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반

을 3개의 기둥 사이에서 옮기는 문제입니다. 모든 원반은 크기가 다르고 처음에는 모든 원반
이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있습니다. 이 상태에서 모든 원반을 세 번째 기둥으로
최소의 횟수로 옮기면 됩니다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을
수 없습니다.

하노이의 탑이라는 알고리즘 이름은 ‘64개의 황금 원반을 3개의 기둥 사이에서 바꿔 옮기는 작업을 완료하면 세계의 종
말이 찾아온다.’라는 고대 인도의 신화에서 유래했습니다.

그림 5-8은 원반이 3개일 때의 모든 과정을 나타낸 것입니다. 차례대로 살펴보면 하노이 탑
의 모든 과정을 충분히 이해할 수 있습니다.

1
2
3 원반 1을 첫 번째 기둥에서 세 번째 기둥으로

2
3 1 원반 2를 첫 번째 기둥에서 두 번째 기둥으로

3 2 1 원반 1을 세 번째 기둥에서 두 번째 기둥으로

1
3 2 원반 3을 첫 번째 기둥에서 세 번째 기둥으로
1
2 3 원반 1을 두 번째 기둥에서 첫 번째 기둥으로

1 2 3 원반 2를 두 번째 기둥에서 세 번째 기둥으로

2
1 3 원반 1을 첫 번째 기둥에서 세 번째 기둥으로
1
2
3
첫 번째 기둥 두 번째 기둥 세 번째 기둥
[그림 5-8] 하노이의 탑(원반 3개)
178 C 알고리즘