BOJ 11729 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729
시간 1초, 메모리 256MB
input :

• N (1 ≤ N ≤ 20)

output :

• 옮긴 횟수 K
• 수행 과정을 출력 ( A B 출력 / A번째 탑의 가장 위 원판 -> B번째 탑의 가장 위로 옮긴다)

조건 :

• 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
• 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

하노이 탑이 움직이는 동작과정.
hanoi(n, from, to)
n개의 원판을 from 기둥에서 to 기둥으로 옮긴다.

재귀의 기저 사례.
가장 위의 원판 1개가 남았을 때 이를 from에서 to기둥으로 옮긴다.

원판들은 언제나 가장 큰 원판 n번 원판을 to 기둥으로 옮겨야하는데 그래서 그 외의 n - 1개의 원판들은 중간의 기둥으로 옮겨져야 한다.
hanoi(n - 1, from, middle)

그러면 중간 기둥을 구하려면 어떻게 하면 되는가?
하노이 탑의 기둥은 3개이다. 1, 2, 3
이 합은 6.
from, to 를 빼주면 middle 기중의 번호를 알 수 있다.

그러면 위의 과정을 해서 나머지 원판들을 중앙에 넣었으니 가장 큰 원판을 to기둥으로 옮긴다.
print("from에서 to로 옮기기")

그 후 hanoi(n - 1, middle, from)으로 옮겨준다.

import sys

n = int(sys.stdin.readline())
result = []

def hanoi(disk, from_, to):
    if disk == 1:
        result.append((from_, to))
    else:
        other_poll = 6 - from_ - to

        hanoi(disk - 1, from_, other_poll)
        result.append((from_, to))
        hanoi(disk - 1, other_poll, to)

hanoi(n, 1, 3)
print(len(result))
for item in result:
    print(item[0], item[1])

https://leedakyeong.tistory.com/entry/%EB%B0%B1%EC%A4%80-python-11729%EB%B2%88-%ED%95%98%EB%85%B8%EC%9D%B4-%ED%83%91-%EC%9D%B4%EB%8F%99-%EC%88%9C%EC%84%9Chanoi-top-in-python

그림이 이뻐서 넣어보았다. 나중에 잊어버리면 다시 읽어봐야지...

맨 처음에 3넣고 하노이 탑 만들다가 n으로 안 바꿔줘서 한 번 틀렸다 ㅋㅋㅋㅋㅋㅋㅋㅋ