하노이 탑 이동 순서

정답 코드

import math

MSG_FORMAT = "{} {}"

N = int(input())


def move(start, to):
    print(MSG_FORMAT.format(start, to))

def hanoi(pan, start, to, via):
    if pan == 1:
        move(start, to)
        return
    hanoi(pan - 1, start, via, to)
    move(start, to)
    hanoi(pan - 1, via, to, start)

print(int(math.pow(2, N) - 1))
hanoi(N, 1, 3, 2)

해결하기 위해 고민했던 아이디어

처음에 스택 3개를 만들어 top의 값을 비교하며 위의 것이 아래의 것보다 작아야 한다는 조건을 만족시키려고 하였다. 스택의 맨 아래에 사용하지 않는 칸 하나를 두어 1,2,3의 베이스 판을 구분할 수 있는 값으로 초기화 하려고 하였다. 하나의 스택을 만들어 옮길때마다 각 스택의 맨 아래의 값을 읽어 어디에서 어디로 옮기는지 식별하고 회수를 함께 저장하려고 하였다.

하지만 위의 방법은 메모리적으로 매우 비효율적이며, 재귀의 특성과는 맞지 않는 방식이라고 확신했고, 하노이 문제를 풀기위한 알고리즘을 생각해보았다.
하지만 그 규칙이 쉽게 떠오르지 않았고, 결국 아래의 블로그를 참고하였다.

참고한 블로그

참고 블로그 요점

1. 문제를 재귀로 해결하기 위해선 hanoi(N)에서 hanoi(N - 1)의 규칙을 찾아야 한다.
2. 횟수를 세는 방법은 알고리즘의 규칙을 바탕으로 일반식을 추론할 수 있어야한다.

   global 변수를 두어 실행시 하나씩 증가하려고 했던 자신을 반성하였습니다...