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

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

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

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

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

2. 참고 그림
   

문제의 분해

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))

지난 7월 30일 자정 즈음 만삭의 아내가 옅은 산통을 호소했다. 혹시나 하는 마음에 괜찮다고 하는 아내를 데리고 병원 응급실을 찾았다. 아니나 다를까 응급실에서 진찰을 받으니 아이가 나올준비를 하고 있으니 입원해야한다고 한다. 두말 할것 없이 곧바로 입원을 했다.

새벽 3시즈음 아내의 산통이 본격적으로 시작되었다. 산통으로 온몸을 부들부들 떠는 아내를 보니 너무나도 미안했다. 아이에겐 말하기 미안하지만 이때 뱃속 아이는 전혀 생각나지 않았다. 그저 아내가 잘못되는 것은 아닌지 내가 대체 아내한테 무슨 몹쓸짓을 한건지 너무 두렵고 불안하고 또 불안했다.

한참의 산통이 지나고 아이가 나올거 같아 분만실로 이동했다. 그리고 다시 힘든 3시간이 지났다.  곧 의사 선생님이 “나온다! 더! 더!” 하고 목소리를 높였고 바로 아이의 울음소리가 터져나왔다. 의사 선생님 손에 들어 올려지는 핏덩이를 보는데 코끝이 시큰했다. 간호사의 안내를 받아 탯줄을 자를때 이미 나는 콧물과 눈물을 질질 짜고 있었다.

탯줄이 잘린 아이는 영아 침대로 옮겨 졌다. 정말 서럽게 우는 그 아이를 보면서 내 의식에는 기묘한 변화가 생겼다. 그리고 보니 이런 기묘한 느낌은 결혼때도 경험 했었다.

나에게 결혼은 쌍성이 탄생하는 느낌이었다. 별 걱정 없이 나를 중심으로 돌던 의식이 아내와 쌍성을 이루며 그 사이에 새로운 중심을 만드는 느낌이었다. 우리 결혼은 나와 아내 사이의 절묘한 균형을 중심으로 돌고 있었다. 나와 아내의 인력 사이의 절묘한 중심이 내가 이해한 결혼 생활이었다.

반면 아이의 탄생은 이 쌍성계을 과감히 해체했다. 아이가 뿜어내는 강력한 인력은 쌍성 사이의 절묘한 균형을 완벽히 압도했다. 서로에 이끌려 돌고 돌던 쌍성계는 더이상 기존의 중심을 유지할 수 없었다. 아이의 강력한 인력에 끌려가버린 쌍성은 이제 아이를 중심으로 돌고 도는 행성계가 되었다.

이제 아이가 태어난지 3주가 되었다. 이제 본격적으로 힘들어 질거라는 주변의 이야기를 나는 아직 이해하지 못하고 있다. 그저 바라보는 것만으로도 행복하다 라는 어머니의 말씀이 이해가기 시작한다.

쓰고 나서 읽어보니 이거 완전 중2병인데 내 실력으론 더이상의 표현이 불가능해서 여기서 접어야겠다.