하노이탑3(4기둥) > 문제은행



알고리즘 백트랙킹2

1405 : 하노이탑3(4기둥)

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 49 회    시도횟수: 296 회    Special Judge



전설의 하노이 탑 문제는 기둥이 3개이다.

 

기둥이 4개인 경우의 문제는 어떻게 될까?

기둥 번호는 차례로 A, B, C, D이고 N개의 원판을 A번 기둥에서 D번 기둥으로 옮겨야 한다.

 

1568문제에서는 이동하는 최소 횟수만 출력하였지만 그 과정도 출력해보자.

 

규칙은 1568문제와 같다.

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

조건 2) 반드시 큰 원판 위에 작은 원판이 있어야 한다. 

조건 3) 각 탑의 맨 위에 있는 원판만 옮길 수 있다. 

 

 

82de47fbe69017d305c733b84f0a7e8e_1457341 

 




첫 줄에 한 정수 n이 입력된다. (단, 1 <= n <= 20 )



첫 번째 줄에 4개의 기둥을 이용하여 옮기는 횟수를 출력한다.
두 번째 줄부터 각 원판을 옮기는 경로를 다음과 같이 출력한다.

원판번호 : 원판이 있던 기둥번호 -> 원판을 이동할 기둥번호

규칙을 지키는 경로가 여러 개라면 아무거나 출력해도 된다.


2
3
1 : A->B
2 : A->D
1 : B->D


참고 :   wiki  


출처 : comkiwer




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.