하노이 탑 문제 정리

Posted on by

읽고있는 파이썬 책에 하노이 탑이 예제로 나왔다. 이거 학생때 배웠던거지! 하며 가벼운 마음으로 보는데 순간 하나도 이해가 되지 않았다. 어떻게 풀었는지도 기억이 나질 않는다. 심지어 소스를 보았는데도 이해가 가지 않는다. 뭐지! 하는 위기감에 정리해 본 하노이 탑 문제.

하노이 탑 ( 출처 : 위키백과 )

  1. 설명
    하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

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

    하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2n-1번의 이동으로 원판을 모두 옮길 수 있다. 메르센 수라고 부른다).참고로 64개의 원판을 옮기는 데 약 18446744073709551615번을 움직여야 하고, 한번 옮길 때 시간을 1초로 가정했을 때 64개의 원판을 옮기는 데 5849억 4241만 7355년 걸린다.

  2. 참고 그림
    300px-Tower_of_HanoiTower_of_Hanoi_4

문제의 분해

  1. 원판이 한개일경우 풀이
    1번 기둥의 1번 원반을 3번 기둥에 옮긴다.
    끝
  2. 원판이 두개인 경우 풀이
    1번 기둥의 1번 원반을 2번 기둥에 옮긴다.
    1번 기동의 2번 원반을 3번 기둥에 옮긴다.
    2번 기둥의 1번 원반을 3번 기둥에 옮긴다.
    끝
  3. 원판이 세개인 경우 풀이
    1 번 기둥의 1 번 원반을 3 번 기둥에 옮긴다.
    1 번 기둥의 2 번 원반을 2 번 기둥에 옮긴다.
    3 번 기둥의 1 번 원반을 2 번 기둥에 옮긴다.
    1 번 기둥의 3 번 원반을 3 번 기둥에 옮긴다.
    2 번 기둥의 1 번 원반을 1 번 기둥에 옮긴다.
    2 번 기둥의 2 번 원반을 3 번 기둥에 옮긴다.
    1 번 기둥의 1 번 원반을 3 번 기둥에 옮긴다.
    끝
  4. 원판이 n개인 경우 풀이
    1번 기둥에서 n-1번 까지의 원판을 2번(여분의 기둥)으로 옮긴다.
    1번 기둥에서 n번 원판을 3번으로 옮긴다.
    2번 기둥의 n-1번 까지의 원판을 3번으로 옮긴다.
    끝

1~4의 과정을 보면 하노이 탑 문제는

hanoi(n) = 2hanoi(n-1) + move(n)

로 정의 될 수 있다. 좀더 상세히 정리를 하면

hanoi(n, startPeg, endPeg) = hanoi(n-1, startPeg, extraPeg) + move(n) + hanoi(n-1, extraPeg, endPeg)

가 된다.

문제 풀이

  1. 리컬시브 구조를 이용한 풀이 
    def hanoiRecursive(ndisks, startPeg=1, endPeg=3):
    global phase
    if ndisks:
        extraPeg = 6 - endPeg - startPeg
        hanoiRecursive(ndisks-1, startPeg, extraPeg)
        print(startPeg, "번 기둥의", ndisks, "번 원반을", endPeg, "번 기둥에 옮깁니다.")
        hanoiRecursive(ndisks-1, extraPeg , endPeg)
  2. Stack을 이용한 풀이 
    def hanoiStack(ndisks, startPeg=1, endPeg=3):
    stack = []
    stack.append((ndisks, startPeg, endPeg, False))
    while len(stack) > 0:
        disks, start, end, move = stack.pop()
        extraPeg = 6 - end - start
        if move:
            print(start, "번 기둥의", disks, "번 원반을", end, "번 기둥에 옮긴다.")
        elif disks > 0:
            stack.append((disks - 1, extraPeg, end, False))
            stack.append((disks, start, end, True))
            stack.append((disks - 1, start, extraPeg, False))

 

11614 Total Views 1 Views Today