재귀 알고리즘의 단골손님, 하노이탑 (Tower of Hanoi)

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.


유래
하노이의 탑은 프랑스의 수학자 뤼카( Édouard Lucas)가 클라우스 교수(professeur N. Claus)라는 필명으로 1883년에 발표하였다. 1년 후 드 파르빌(Henri de Parville)은 Claus가 Lucas의 애너그램임을 밝히면서 다음과 같은 이야기로 하노이의 탑을 소개하였다.

인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다.
참고로, 스님들이 순금원판을 다른 바늘로 모두 옮기는 시간은, 한 번에 1초씩 걸린다고 쳐도 대략 5천 8백억 년 이상 이라는 계산이 나옵니다. (2의 64승 - 1)은 18,446,744,073,709,551,615.

뤼카가 하노이의 탑(tours de Hanoï)이라는 이름을 붙인 이유는 명확하지 않으나, 당시 프랑스의 식민지였던 베트남 하노이를 상징하는 국기탑에서 유래하였을 것으로 추정된다.

이후 라우즈 볼, 가드너 등이 하노이의 탑을 소개하면서 널리 알려졌다.

(출처 : 위키백과 http://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91)



재귀호출 알고리즘을 언급할 때 단골로 등장하는 예제가 하노이탑인 것 같네요. 6층 탑을 옮길 때  맨 밑바닥의 판을 옮기려면 맨 밑바닥 판 위에 쌓여있는 5층 탑을 다른 곳에 옮겨놓아야 하고, 그 5층 탑을 옮길 때 맨 밑바닥의 판을 옮기려면 쌓여있는 4층 탑을 다른 곳에 옮겨야 하기 때문에 재귀를 사용하기 적합합니다.

널리 잘 알려져있고, 파는 곳이 많아 구하기 쉬운 완구입니다. 파는 곳에 따라 조금씩의 디자인의 차이는 있습니다만.. 원판 수가 n일 때 필요한 옮기는 회수의 최소값은 2의n승-1 입니다. 군대에 있을 때 말년에 할일이 없어.. 엑셀에 있는 VBA를 이용해 하노이탑을 만들어 즐겼던 기억이 나네요.

'원판을 한번에 두칸을 이동할 수 없다.' 라는 규칙을 추가해도 풀이가 가능합니다. 기둥이 4개일 때 줄어든 최소값을 구해보는 것도 재밌겠네요.

파일 다운로드

하노이탑.exe

하노이탑을 간단하게 해볼수 있는 실행파일입니다.
(출처 : http://www.sciencelove.com)