PS/Python
[Python] 백준(BOJ) 11729번: 하노이 탑 이동 순서 - 재귀
yoo.o
2020. 10. 26. 03:24
반응형
문제
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
풀이
하노이탑의 이동 횟수는 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)
반응형