[백준/Python] 하노이 탑 이동 순서

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

 

# 하노이 탑 알고리즘

1. 1번 기둥의 n-1 개의 원반을 2번 기둥으로 옮긴다.

2. 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다.

3. 2번 기둥의 n-1개의 원반을 3번 기둥으로 옮긴다.

 

1

2

3

 

num = int(input())

def hanoi(n, p_from, p_to, p_mid):
	if n == 1: # 원반이 1개이면 무조건 원반을 1번에서 3번으로 옮긴다.
		print(p_from, p_to)
		return

	hanoi(n-1, p_from, p_mid, p_to) # 1번 기둥의 n-1 개의 원반을 2번 기둥으로 옮긴다
	print(p_from, p_to) # 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다
	hanoi(n-1, p_mid, p_to, p_from) # 2번 기둥의 n-1개의 원반을 3번 기둥으로 옮긴다

print(2**num-1) # 이동 횟수 = 2^num - 1
hanoi(num, 1, 3, 2)

 

[ 사진 출처 ]

https://stricky.tistory.com/155

파이썬 재귀호출 알고리즘 하노이의 탑 옮기기 #6