하노이의 탑

재귀에 관한 수업을 다 마쳤다면 이제 재귀 과정을 여러번 거쳐 푸는 다른 문제에 대해 알아봅시다. 이는 하노이 탑이라고 불리는 문제입니다. 세 개의 축과 $n$‍개의 원반이 주어지는데 각각의 원반은 크기가 상이합니다. 축을 A, B, C라고 부르기로 하고 원반은 가장 작은 원반을 1로, 가장 큰 원반을 $n$‍이라고 번호를 매긴다고 합시다. 처음에는 모든 $n$‍개의 원반이 크기 순서대로 위에서 아래로, 즉 1이 가장 위에, 그리고 $n$‍이 가장 아래인 상태로 축 A에 놓여 있습니다. 원반이 $n=5$‍개인 하노이 탑은 다음과 같습니다.

목표는 모든 $n$‍개의 원반을 축 A에서 축 B로 옮기는 것입니다.

쉬워보이죠? 그렇지만 그렇게 쉽지는 않은데, 다음 두 가지 규칙을 지켜야 하기 때문입니다.

이 문제가 그다지 중요한 것은 아니라고 생각할 수 있습니다. 하지만 실제는 그렇지 않습니다! 전설에 따르면 아시아 어딘가(티벳, 베트남, 인도—인터넷에 있는 전설 중 마음대로 고르세요) 수도승들이 이 문제를 64개의 원반으로 풀어보려고 했다고 합니다. 이 이야기에서는 수도승들이 축 A에서 축 B으로 64개의 원반 모두를 옮기게 되면 세상이 끝날 것이라고 믿었다고 합니다. 수도승들이 맞다면 우리는 거리에서 공포에 떨며 헤매고 있어야 하겠군요.

우선 이 문제를 재귀적으로 어떻게 풀지 알아봅시다. 정말 쉬운 경우부터 시작해 봅시다: 원반 하나 즉 $n=1$‍인 경우입니다. $n=1$‍인 경우가 이 문제의 탈출 조건입니다. 언제든 원반 1을 축 A에서 축 B로 옮길 수 있습니다. 원반 밑에는 더 큰 숫자의 원반이 있어야 한다는 조건은 항상 만족되기 때문입니다. 축 A와 축 B가 특별할 것은 없습니다. 원한다면 원반 1을 축 B에서 축 C로, 또는 축 C에서 축 A로, 어느 축에서나 다른 축으로 옮길 수 있습니다. 하나의 원반으로 된 하노이의 탑 문제는 단지 한 번에 하나의 원반을 움직이기만 하면 됩니다.

원반이 두 개일 경우는 어떨까요? $n=2$‍일 경우는 어떻게 문제를 풀 수 있을까요? 3단계로 풀 수 있습니다. 아래는 시작할 때의 상태입니다.

먼저 원반 1을 축 A에서 축 C로 옮깁니다.

축 C를 나머지 축으로 이용하여 원반 1을 잠시 꽂아놓음으로써 원반 2를 꺼낼 수 있게 합니다. 이제 가장 바닥에 있던 원반 2가 위로 나왔습니다. 이것을 축 B로 옮깁니다.

마지막으로 원반 1을 축 C에서 축 B로 옮깁니다.

이 해법은 3단계로 이루어집니다. 다시 한번 말하지만 두 개의 원반을 꼭 축 A에서 축 B로 옮기지 않아도 됩니다. 축 A를 나머지 축으로 이용하고 축 B에서 축 C로 옮겨도 됩니다. 원반 1을 축 B에서 축 A로 옮긴 후 원반 2를 축 B에서 축 A로 옮기고 마지막으로 원반 1을 축 A에서 축 C로 옯깁니다. 원반 1과 2를 특정 축에서 다른 축으로 3단계만에 옮길 수 있다는 것에 동의하시나요? ("네"라고 해 주세요)

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.