2002년 가을학기 문제해결기법 - 문제 4

하노이 탑

원래의 하노이 탑 문제는 말뚝이 3개 있고, 크기가 서로 다른 n개의 디스크가 하나의 말뚝에 놓여 있을 때, 이 디스크들을 아래 조건을 만족하면서 다른 하나의 말뚝으로 옮기는 것이다.

C1. 맨 위에 놓여 있는 디스크를 한번에 하나씩 다른 말뚝으로 옮길 수 있다.

C2. 큰 디스크를 작은 디스크 위에 놓아서는 안 된다.

디스크가 하나의 말뚝에 놓여있지 않고 아래 그림과 같이 조건 C2를 만족하면서 여러 개의 말뚝에 흩어져 있을 수 있을 때, 하나의 말뚝으로 옮겨서 모으는 프로그램을 작성하시오. 이 때 디스크를 옮기는 횟수는 을 넘어서는 안 된다.

|                |                |

|                |                |

|                |                |

|                |                |

[==2==]           [=1=]              |

[====4====]       [===3===]            |

-------------    -------------     -------------

말뚝 1          말뚝 2          말뚝 3

프로그램명은 hanoi.xxx라고 하고 실행 파일명은 hanoi.exe로 한다. 프로그램의 실행 시간은 10초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 줄에 디스크의 수 n과 최종적으로 디스크를 쌍아야 하는 목적 말뚝 번호 p가 입력된다. 디스크의 크기를 순서대로 1, 2,  ..., n이라고 한다. n은 모두 12 이하인 정수이다. 둘째 줄에 말뚝 1에 놓여 있는 디스크의 수와 디스크 번호가 위에서 아래로 차례로 주어진다. 마찬가지 방식으로 셋째 줄과 넷째 줄에 각각 말뚝 2와 3에 놓여 있는 디스크가 주어진다. 한 줄에 두개 이상의 정수가 입력되는 경우, 정수들 사이에는 공백이 있다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 만약 디스크를 모을 수 없거나 혹은 가능하더라도 회 이하로 불가능하면 첫째 줄에 -1을 출력하고 끝낸다. 그렇지 않으면 먼저 첫째 줄에 디스크를 옮긴 횟수 k를 출력한다. 둘째 줄부터 마지막 줄까지 k개의 줄에 디스크의 이동을 차례로 출력한다. 각 줄에는 두 정수 a, b를 콤마 없이 출력하는데, 이것은 말뚝 a의 맨 위 디스크를 말뚝 b로 옮긴다는 것을 뜻한다.

입력과 출력의 예

INPUT.TXT

4 1

2 2 4

2 1 3

0

OUTPUT.TXT

6

1 3

2 3

2 1

3 2

3 1

2 1