백준 / 하노이 탑 이동순서 / 11729

Question

문제링크
Silver 1

Logic

기본 구조 : recursion

1. 하노이 탑은 다음과 같다.
   

2. 시작 지점 1을 s, 목적지 3을 d, 중간지점 2를 t라 한다.

3-1. N=2일때, 두번 째 디스크를 3으로 보내려면 우선 첫번 째 디스크를 2로 보내야 한다. (1 2).
3-2. 그 후 두번 째 디스크를 옮기고(1 3),
3-3. 다시 첫번 째 디스크를 최종 목적지로 옮긴다(2 3).
4. 이를 일반화하면, N개를 S에서 D로 옮기기 위해서는, 우선 N-1개를 S에서 T로 옮긴 다음, S에서 D로 1회 이동하고, 다시 N-1개를 T에서 D로 이동해야 한다.
5. 이를 재귀로 표현하면 아래와 같다.

Code

from sys import stdin
S,T,D = '1','2','3'
res=[]
def hanoi(n,s,d,t):
    if n==0 : return
    hanoi(n-1,s,t,d)
    res.append(s+' '+d)
    hanoi(n-1,t,d,s)

N = int(stdin.readline().rstrip())
hanoi(N,S,D,T)
print(len(res))
print('\n'.join(res))