11729 - 하노이 탑 이동 순서
1. 개요
https://www.acmicpc.net/problem/11729
2. 코드
Python3
1
2
3
4
5
6
7
8
9
10
11
12
13
import sys
def hanoi(n, source, to, sub):
if n == 1:
print(source, to)
return
hanoi(n-1, source, sub, to)
print(source, to)
hanoi(n-1, sub, to, source)
N = int(sys.stdin.readline())
print(2**N-1)
hanoi(N, 1, 3, 2)
3. 설명
- 맨 처음에 이동에 필요한 횟수를 출력하고, 이동 순서를 찾기 위한 재귀 탐색을 실시한다.
- 재귀 탐색 알고리즘
- 원반이 한 개면 그냥 옮길 수 있다.(종료 조건)
- 원반이 n개일 때
- 1번 기둥에 있는 n개 원반 중 n-1개를 2번 기둥으로 옮긴다.(3번 기둥은 보조)
- 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다.(출력)
- 2번 기둥에 남아 있는 n-1개 원반을 다시 3번 원반으로 옮긴다.(1번 기둥은 보조)
4. 여정
- 통과
5. 결과
