1하노이의 탑

 

하노이의 탑(Tower of Hanoi)은 간단한 원반(disk) 옮기기 퍼즐입니다. 규칙을 설명하기 전에 그림 6-1을 봅시다.

 

그림 6-1 하노이의 탑 (출처: https://en.wikipedia.org/wiki/Tower_of_Hanoi)

 

그림만 봐도 대강 규칙이 떠오르지 않나요?

하노이의 탑에는 크기가 다른 원반이 n개 있고 원반을 끼울 수 있는 기둥이 세 개 있습니다. 하노이의 탑 문제는 어떻게 하면 원반 n개를 모두 가장 왼쪽 기둥(출발점, 즉 1번 기둥)에서 오른쪽 기둥(도착점, 즉 3번 기둥)으로 옮길 수 있을까 하는 문제입니다.

단, 하노이의 탑을 옮길 때는 세 가지 제약 사항이 있습니다. 원반은 한 번에 한 개씩만 옮길 수 있고, 각 기둥 맨 위의 원반을 다른 기둥의 맨 위로만 움직여야 합니다. 옮기는 과정에서 큰 원반을 작은 원반 위에 올려서는 안 됩니다. 이 규칙을 지키면서 원반을 옮기려면 중간에 여분으로 주어진 보조 기둥(2번 기둥)을 잘 활용해야 합니다.