백준#11729 - 하노이의 탑
문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입출력 규칙
1. 입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
2. 출력
- 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
- 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
문제 접근
1. 한번에 한개의 원판만 이동이 가능하다.(두개 이상씩 한꺼번에 옮길 수는 없다)
2. 쌓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.(크기가 역전될 수는 없다)
3. 그림 상 1번 위치가 시작점, 2번이 보조, 3번이 목표점이다. 세개의 공간을 활용해 원판을 한개씩 계속 옮겨가는(재귀) 함수를 구현한다.
4. 총 몇번을 움직이는지, 각각의 원판이 어떤 순서로 움직이는지를 출력하자.
참조 YouTube
코드
def hanoi(n, frm, to, otr):
if n < 2:
print(frm, to) # frm에서 to로 이동
return
hanoi(n-1, frm, otr, to) # 맨 아래칸을 제외하고 frm에서 otr로 재귀적 이동
print(frm, to) # 맨아래 원반 목적지로 이동
hanoi(n-1, otr, to, frm) # otr로 옮겼던 원반 to로 이동
n = int(input())
print((2**n)-1)
hanoi(n, 1, 3, 2)
뿝