하노이탑 함수

하노이탑 (The Tower of Hanoi)

한번에 하나의 원판만 옮길 수 있으며 큰 원판이 작은 원판 위에 있어서는 안된다. 는 두 가지 조건을 만족시키며 한 기둥에 꽃힌 원판을 순서 그대로 다른 기둥에 옮겨 쌓는 퍼즐이다.

재미있는 가짜 전설도 있다.

순환

하노이탑 문제는 순환의 힘을 제일 잘 보여주는 예제라고 한다.

소스코드

def hanoi(n, frm, tmp, to):
    if n == 1:
        print("원판 1을 {0} 에서 {1}으로 옮긴다.".format(frm, to))
    else:
        hanoi(n-1, frm, to, tmp)
        print("원판 {0}을 {1} 에서 {2}으로 옮긴다.".format(n, frm, to))
        hanoi(n-1, tmp, frm, to)

hanoi(4, 'a', 'b', 'c')

출력

원판 1을 a 에서 b으로 옮긴다.
원판 2을 a 에서 c으로 옮긴다.
원판 1을 b 에서 c으로 옮긴다.
원판 3을 a 에서 b으로 옮긴다.
원판 1을 c 에서 a으로 옮긴다.
원판 2을 c 에서 b으로 옮긴다.
원판 1을 a 에서 b으로 옮긴다.
원판 4을 a 에서 c으로 옮긴다.
원판 1을 b 에서 c으로 옮긴다.
원판 2을 b 에서 a으로 옮긴다.
원판 1을 c 에서 a으로 옮긴다.
원판 3을 b 에서 c으로 옮긴다.
원판 1을 a 에서 b으로 옮긴다.
원판 2을 a 에서 c으로 옮긴다.
원판 1을 b 에서 c으로 옮긴다.

함수를 중위순회 하도록 순환호출 알고리즘을 구성하면 신기하게도 조건을 지켜가며 원판을 이동시킨다.

시간복잡도

총 n-1 번 2개의 문제들로 나뉘게 되므로 복잡도는 O(2ⁿ) 가 된다.