문제 설명
평소 하노이의 탑 게임을 즐기는 DH씨는 원판의 개수만 알아도 각 원판의 최단 경로를 순서대로 설명할 수 있다.
이런 DH씨의 능력을 본 딴 프로그램을 만들어보자.
[참고자료]
하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.
게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.
- 한 번에 하나의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안 된다.
하노이의 탑 문제는 재귀 호출을 이용하여 풀 수 있는 가장 유명한 예제 중의 하나이다. 그렇기 때문에 프로그래밍 수업에서 알고리즘 예제로 많이 사용한다. 일반적으로 원판이 n개 일 때, 2n -1번의 이동으로 원판을 모두 옮길 수 있다(2n − 1는 메르센 수라고 부른다).
참고로 64개의 원판을 옮기는 데 약 18446744073709551615번을 움직여야 하고, 한번 옮길 때 시간을 1초로 가정했을 때 64개의 원판을 옮기는 데 5849억 4241만 7355년이 걸린다. (출처: 위키백과 CC-BY-SA)
입력 설명
원판의 개수 n이 입력된다. (1 ≤ n ≤ 10 )
출력 설명
원판의 최단 이동 경로를 아래와 같이 출력하시오.
(예 - 1번 원판이 A 기둥에서 B 기둥으로 이동하는 경우) 1 : A -> B
(예 - 1번 원판이 A 기둥에서 B 기둥으로 이동하는 경우) 1 : A -> B
입력 예시 Copy
3
출력 예시 Copy
1 : A -> C
2 : A -> B
1 : C -> B
3 : A -> C
1 : B -> A
2 : B -> C
1 : A -> C