문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
예제 입력
3
예제 출력
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
풀이
동작 구조를 재귀적으로 이해하기 위해 n개의 원판이 있는 경우를 생각해보았다.
3개를 목적지로 옮기는 과정
= 2개를 목적지(처음->중간)로 옮기는 과정 + 1 + 2개를 목적지(중간->마지막)로 옮기는 과정
= 1개를 목적지(처음->마지막)로 옮기는 과정 + 1 + 1개를 목적지(처음->중간)로 옮기는 과정
+ 1개를 목적지(중간->처음)로 옮기는 과정 + 1 + 1개를 목적지(중간->마지막)로 옮기는 과정
과정을 보면 시작 지점과 목적지가 달라지는 것을 볼 수 있다. 따라서 재귀적으로 수행하되, 재귀함수 내부에서 재귀호출을 할때는 시작 지점과 목적지를 상황에 맞게 설정하여 호출해줘야 한다.
원판을 옮기는 자료구조를 실제로 구현할 필요는 없다. 재귀적으로 한개의 원판이 남아있는 경우일 때, 해당 원판을 어디로 옮겨야 하는지만 알면 된다. 따라서 hanoi(first,end,mid,n-1) # 제일 아래를 제외한 부분을 중간으로 옮김 이 코드 다음이 원판이 한개만 존재하는 경우이므로 이때의 first와 end 를 출력해주면 된다.
*옮길 원판이 한개도 없는 경우에는 return 을 해준다. 이를 위해 현재 옮길 원판의 개수를 재귀적으로 전달해준다.
n = int(input()) # 현재 옮겨야 할 원판의 개수
cnt = 0
ans = []
def hanoi(first,mid,end,n):
global cnt
if n == 0: return
hanoi(first,end,mid,n-1) # 제일 아래를 제외한 부분을 중간으로 옮김
cnt+=1 # 제일 밑 원판을 마지막으로 옮김
ans.append((first,end))
hanoi(mid,first,end,n-1) # 중간에 옮겨진 것들을 마지막으로 옮김
hanoi(1,2,3,n)
print(cnt)
for f,e in ans: print(f,e)