Informatica Online Judge

  하노이탑의 확장 [1225 / 04C9]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 24   Total Tried : 130


The Champion of this Problem (C++) : gst19001 - ms / 1312byte
My Best Submission (C++) : N/A

[JKJeong 2015]
Writer ID : [jkjeong]

Background

하노이 타워는 n개의 원판과 3개의 기둥으로 구성되어 있으며,

가장 왼쪽의 기둥에 위치한 n개의 원판을 가장 오른쪽 기둥으로 다음 규칙을 지키면서 최소 이동 횟수로 옮기는 게임이다.

규칙 1. 한 번에 하나의 원판만 옮길 수 있다.
규칙 2. 작은 원판 위에 큰 원판을 옮길 수 없다.

이 게임은 다양한 버전의 변종들이 등장한다.

이번에 주어진 게임은 하노이 타워의 기둥 확장버전이다.

이번에는 3개의 원판과 기둥이 n개 주어진다. 그리고 각 기둥 간에 원판을 옮기는데 드는 비용이 정해져 있다.

즉 각 기둥들 사이의 관계가 그래프의 형태로 이루어져 있다.

각 기둥 간 옮기는 가중치가 인접행렬의 형태로 주어진다.
(이 그래프는 양방향 그래프이다. 즉, W[i][j] == W[j][i] )

각 기둥의 관계와 출발 기둥과 도착 기둥이 차례로 주어질 때,

출발 기둥에 있는 3개의 원판을 위 규칙1, 규칙2를 지켜가면서 도착 기둥으로 옮기는 최소 가중치를 구하는 프로그램을 작성하시오.

단, 원판을 옮길 때에는 기둥과 연결된 기둥(인접한 기둥)으로만 옮길 수 있다.

예를 들어 다음은 기둥이 3개 있고 각 기둥 간 가중치가 1인 예를 보여준다.



만약 이 경우 1번 기둥에서 3번 기둥으로 옮기려면


가장 작은 원판을 1에서 3으로 옮긴다. - 가중치 누적 1

두 번째 작은 원판을 1에서 2로 옮긴다. - 가중치 누적 2

가장 작은 원판을 3에서 2로 옮긴다. -가중치 누적 3

가장 큰 원판을 1에서 3으로 옮긴다. - 가중치 누적 4

가장 작은 원판을 2에서 1로 옮긴다. - 가중치 누적 5

두 번째 작은 원판을 2에서 3으로 옮긴다. - 가중치 누적 6

가장 작은 원판을 1에서 3으로 옮긴다. - 가중치 누적 7


이와 같은 방법으로 옮기면 7의 가중치로 3개의 원판을 1에서 3으로 옮길 수 있다.

이 보다 더 적은 가중치로 모두 옮길 수 있는 방법은 없으므로 답은 7이다.

다음과 같은 확장 하노이 타워가 주어진다면??? 어떻게 해결해야 할까?



이를 해결하는 프로그램을 작성하시오.

Input

첫 번째 줄에 기둥의 수 n이 입력된다.

다음 줄부터 n줄에 걸쳐서 각 n개의 자연수가 입력된다.

이 테이블은 각 기둥간 이동에 대한 가중치를 나타낸다. (단, 0이면 이동 불가능!!)

다음 줄에 시작 기둥의 번호와 도착 기둥의 번호가 공백으로 구분되어 입력된다.

[Sub-task Info]
#1 : n <= 5
#2 : n <= 30

가중치는 모두 10,000이하의 자연수

Output

3개의 원판을 시작 기둥에서 마지막 기둥까지 모두 옮기는데 드는 최소비용을 출력한다.

IO Example

입력
3
0 1 1
1 0 1
1 1 0
1 3

출력
7

* 설명 : 위 설명의 예이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]