A, B, C 세개의 기둥이 있을 때, N개의 원판을 A번 기둥에서 C번 기둥으로 이동하는

일반적인 하노이 규칙에 다음과 같이 3번 규칙을 추가한 경우를 보자.

1. 한 번에 하나의 원판만 옮길 수 있다.

2. 큰 원판이 작은 원판 위에 있을 수 없다.

3. 가능한 가장 긴 단순 경로(simple path)를 이용하여 원판을 옮겨야 한다.

(단순 경로란 이전과 같은 상태를 다시 거치지 않는 경우를 말한다.)

예를 들어 아래 그림과 같이 A번 기둥에 2개의 원판이 쌓여 있는 경우를 생각해 보자.

위 모습을 순서쌍으로 나타내면 (12, 0, 0) 이라고 하자.

이를 이용하여 우리가 원하는 최종 상태를 나타내면 (0, 0, 12) 이다.

위 3가지 규칙에 따라 가장 긴 단순 경로를 구한 예는 다음과 같다.

( 2, 1, 0) 1번 원판이 A기둥에서 B기둥으로 1 : A->B

( 2, 0, 1) 1번 원판이 B기둥에서 C기둥으로 1 : B->C

( 0, 2, 1) 2번 원판이 A기둥에서 B기둥으로 2 : A->B

( 0,12, 0) 1번 원판이 C기둥에서 B기둥으로 1 : C->B

( 1, 2, 0) 1번 원판이 B기둥에서 A기둥으로 1 : B->A

( 1, 0, 2) 2번 원판이 B기둥에서 C기둥으로 2 : B->C

( 0, 1, 2) 1번 원판이 A기둥에서 B기둥으로 1 : A->B

( 0, 0,12) 1번 원판이 B기둥에서 C기둥으로 1 : B->C

가장 긴 단순 경로는 8

모든 원판이 A번 기둥에 순서대로 쌓여 있을 때,

위 규칙에 따라 C번 기둥으로 모두 이동하는 과정을 순서대로 출력하는 프로그램을 작성하시오.

하노이8(가장긴 하노이) timer 1s memory 256MB

하노이8(가장긴 하노이) 1s 256MB