세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
하노이 탑 사진
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
내 풀이
1. 가장 밑 원판을 목적지로 옮기려면 위에 가장 밑 원판 위에 있는 원판을 출발지도 목적지도 아닌 곳으로 옮겨야 한다. (문제축소)
5원판을 A에서 C로 옮기려면 4원판을 A에서 B로 옮겨야 한다.
4원판을 A에서 B로 옮기려면 3원판을 A에서 C로 옮겨야 한다.
...
n원판을 A에서 C로 옮기려면 n-1원판을 A에서 B로 옮겨야 한다.
마지막 원판이 옮겨지면 재귀를 종료한다. (종료조건)
2. 첫 번째 재귀 호출이 끝났다면 원판을 옮겨준다. (원판 하나만 옮긴 상태)
3. 우리의 목적은 탑 자체를 옮기는 것이기 때문에 다시 재귀 호출을 통해 위의 원판들을 해당 원판 위로 옮겨준다.
Ex) 4원판이 B로 옮겨졌을 때, 3, 2, 1 원판도 B로 옮겨져야 한다.
코드
import sys
def hanoi(n, start, sub, end) :
if n > 1 :
hanoi(n-1, start, end ,sub)
print(start, end)
if n > 1 :
hanoi(n-1, sub, start, end)
N = int(sys.stdin.readline().rstrip())
print(2**N - 1)
hanoi(N,1,2,3)
