[Python] 백준(BOJ) 11729번: 하노이 탑 이동 순서 - 재귀

문제

11729번: 하노이 탑 이동 순서

풀이

하노이탑의 이동 횟수는 2^n -1 이며

하노이탑 이동 시뮬레이션은 함수로 따로 구현했다.

 

1번탑의 원반들을 3번탑으로 옮겨야할때 재귀적 방법으로

n개의 원반중 가장 아래 한개를 제외한 n-1개를 2번탑으로 옮긴 후,

남아있는 1개의 원반을 3번으로 옮기고

2번으로 옮겨둔 n-1개의 원반을 다시 3번 탑으로 옮기면 된다. 

import sys

# num: 옮겨야하는 수 / f: from / b: 거쳐서 / t: to
def hanoi(num, f, b, t):
    if num == 1:
        print(f, t)
    else:
        hanoi(num-1, f, t, b)
        print(f, t)
        hanoi(num-1, b, f, t)

num = int(sys.stdin.readline())
print(2**num - 1)
hanoi(num, 1, 2, 3)