하노이의 탑 텍스트 버전 ( The Tower of Hanoi, text version)

이번에도 꽤 유명한 문제인 하노이 탑에 대해 얘기해보려고 한다. 처음 내가 하노이탑 문제를 접했을 때는 초등학생 때였던 걸로 기억한다. 몇 명을 모아두고서 선생님이 하노이탑 움직임에 대해 설명해준 후 제일 적은 횟수로 움직여서 원반을 모두 옮긴 사람에게 상을 주는 게임을 했었다. 최적화된 정답이 있는 상태로 놀림당한 격이다ㅋㅋㅋㅋ

혹시 너무 오랜만에 접했거나 처음 이 문제를 읽게 된 사람은 하노이탑 링크 ( wiki ) 를 확인해보기 바란다.

하노이탑 문제를 푸는 알고리즘을 수학적으로 분석하는 방법은 고등학교 때 처음 접했다. 수열을 만들어서 해를 구해보니 O( 2^n ) 시간복잡도를 가지게끔 되더라. 오늘은 그 방법을 재귀 함수로 구현해보고자 한다.

---

[문제]

숫자 n을 입력받아, 하노이탑 원반 n개를 1회 옮기는 과정을 출력하라.

[예시]

# definition
def hanoi(src, dst, tmp, num):
    if num > 0:
        hanoi(src, tmp, dst, num-1)
        print "DISC [ %s ] moves %s -> %s"%( str(num), src, dst )
        hanoi(tmp, dst, src, num-1)
 
# run
tower_src = raw_input("Input name of departure tower: ")
tower_dst = raw_input("Input name of destination tower: ")
tower_tmp = raw_input("Input name of one additional tower: ")
 
flag = True
while flag:
    try:
        tower_num = int(input("How many discs? "))
        flag = False
    except:
        print "Please input a integer number"
    
hanoi(tower_src, tower_dst, tower_tmp, tower_num)

14줄부터 있는 while, try except 부분은 빼도 좋다. 그냥 tower_num 을 입력받기 위해서 조작한 부분이다. 여기서 정수만 제대로 입력하면 된다.

분석할 부분은 2줄의 hanoi 함수이다. src는 source의 약자, dst는 destination, tmp는 temporary의 약자이다. 각각 원반 움직임이 시작될 탑, 도착할 탑, 그리고 나머지 탑의 이름을 입력하는 식이다. str 형식으로 넣으면 된다. 재귀 함수가 더이상 아무 일도 하지 않을 조건으로 옮길 타워의 개수인 num이 0인 것으로 잡았다. 0개의 타워를 움직이라는 명령은 의미가 없기 때문이다.

하노이 탑의 수열을 분석할 때처럼 생각해보면 쉽다. 어떤 알고리즘 S 가 존재해서 하노이탑 문제를 풀 수 있다고 가정하자. 이러한 해를 hanoi함수로 구현한 것이다.

하노이탑에 n개의 원반이 있을때, n-1개의 원반을 나머지 탑 (tmp) 에 옮기고 / 4줄

마지막 원반 1개를 목적지 탑 (dst) 에 옮긴 다음 / 5줄

나머지 탑 (tmp) 에서 목적지 탑 (dst) 로 n-1개의 원반을 새로 옮기면 된다. / 6줄

재귀 함수 단골 문제인 만큼 매우 좋은 예시이고 익혀놓아야할 중요한 문제이다.