섬 순회

300점케이스 16출제 dongbinna

10월 30일에 올라온 문제입니다.

문제

바다에 1번부터 N번까지 번호가 붙은 N개의 섬이 있다. 보급선은 1번 섬에서 출발해 나머지 모든 섬을 한 번씩 들른 뒤에 다시 1번 섬으로 돌아와야 한다. 한 번 들른 섬에는 다시 들르지 않는다.

두 섬 사이에는 뱃길이 놓여 있을 수도 있고, 놓여 있지 않을 수도 있다. 또한 뱃길을 지나는 데 드는 연료는 가는 방향에 따라 다를 수 있다. 조류 때문에 i번 섬에서 j번 섬으로 가는 데 드는 연료와, j번 섬에서 i번 섬으로 가는 데 드는 연료가 서로 다른 것이다.

보급선이 들르는 차례를 잘 정해서 한 바퀴를 도는 데 드는 연료의 합을 가장 작게 만들었을 때, 그 연료의 합을 구하는 프로그램을 작성하여라.

예를 들어 N=4이고, 섬 사이의 연료가 다음의 표와 같다고 해보자. 각 행은 출발하는 섬, 각 열은 도착하는 섬을 뜻한다.

출발하는 섬	1번으로	2번으로	3번으로	4번으로
1번	0	10	15	20
2번	5	0	9	10
3번	6	13	0	12
4번	8	8	9	0

1번 섬에서 출발해 나머지 세 섬을 한 번씩 들르고 돌아오는 차례는 모두 6가지이며, 각 차례에 드는 연료의 합은 다음의 표와 같다.

들르는 차례	연료의 합
1번, 2번, 3번, 4번, 1번	39
1번, 2번, 4번, 3번, 1번	35
1번, 3번, 2번, 4번, 1번	46
1번, 3번, 4번, 2번, 1번	40
1번, 4번, 2번, 3번, 1번	43
1번, 4번, 3번, 2번, 1번	47

두 번째 차례를 따라가 보자. 1번에서 2번으로 10, 2번에서 4번으로 10, 4번에서 3번으로 9, 3번에서 1번으로 6이 들어 합이 35가 된다. 이 값이 여섯 가지 가운데 가장 작으므로, 이 예시에서 정답은 35이다.

표의 값이 0인 자리는 그 방향으로 가는 뱃길이 없다는 뜻이다. 뱃길이 없는 방향으로는 지나갈 수 없으므로, 그 방향을 쓰는 차례는 아예 셈에서 빠진다. 모든 섬을 한 번씩 들른 뒤에 1번 섬으로 돌아오는 차례는 적어도 하나 존재한다.

입출력 예시

예시 1

입력

출력

예시 2

입력

2
0 824230
864553 0

출력

예시 3

입력

5
0 26 37 19 0
50 0 12 0 64
87 79 0 33 26
39 0 67 0 23
0 46 37 48 0

출력

입력 조건

가장 먼저 섬의 수 N이 자연수로 주어진다. N은 2 이상 10 이하의 자연수다.
이어서 N개의 줄에 걸쳐 섬 사이의 연료 정보가 주어진다. i번째 줄의 j번째 수는 i번 섬에서 j번 섬으로 가는 데 드는 연료를 뜻하며, 한 줄의 수는 공백을 기준으로 구분되어 주어진다. 값이 0이면 그 방향으로 가는 뱃길이 없다는 뜻이다. 따라서 i번째 줄의 i번째 수는 언제나 0이다. 0이 아닌 값은 1,000,000보다 작은 자연수다.

출력 조건

보급선이 한 바퀴를 도는 데 드는 연료의 합의 최솟값을 첫째 줄에 자연수로 출력한다.
출력하는 수 뒤에는 줄바꿈 하나만 붙는다. 수 앞이나 뒤에 공백을 붙이지 않고, 줄바꿈 뒤에 빈 줄을 더 붙이지도 않는다.

요구사항

1번 섬에서 출발해 모든 섬을 한 번씩 들른 뒤 1번 섬으로 돌아옵니다
한 번 들른 섬에는 다시 들르지 않습니다
가는 방향에 따라 드는 연료가 다를 수 있습니다
값이 0인 방향으로는 지나갈 수 없습니다
모든 섬을 한 번씩 들르고 돌아오는 차례는 적어도 하나 존재합니다
표준 입력으로 읽고 표준 출력으로 내보내는 프로그램을 짜야 합니다
쓸 수 있는 말은 파이썬, 자바스크립트입니다
메모리 제한은 256MB입니다. 브라우저에서는 재지 않고 적기만 합니다
시간 제한은 출제자의 정답 코드를 같은 런타임에서 재서 정합니다
이 문제는 프롬프트가 아니라 코드를 냅니다. 그 코드는 이 기기의 브라우저에서 돌고, 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다. 실행 시간은 각자 기기가 적어 보내는 값이라, 코드와 기기 정보를 순위표에 같이 내걸어 둡니다.
출력이 글자 하나까지 기대값과 같아야 합니다. 줄 안의 빈칸은 다른 글자와 똑같이 봅니다.
케이스는 16개이고, 그 가운데 3개는 입력과 기대 출력을 함께 보여 줍니다. 나머지는 제출할 때만 쓰이고 화면에는 보여 주지 않습니다.
케이스 16개를 전부 통과해야 해결입니다.

문제의 요구 사항을 잘 읽고 해결해 주세요. 단, 채점 과정을 건드려 통과한 것처럼 꾸미는 경우 적발 시 제재될 수 있습니다. 제출한 코드는 순위표에 함께 공개됩니다.

예시

공개 케이스 3개입니다. 채점에는 숨은 케이스가 함께 쓰입니다. 케이스 16개를 전부 통과해야 해결입니다.

입력

기대 출력

2
0 824230
864553 0

5
0 26 37 19 0
50 0 12 0 64
87 79 0 33 26
39 0 67 0 23
0 46 37 48 0

풀이

코드는 이 기기에서돕니다. 서버로는 나온 출력의 지문과 걸린 시간만 갑니다. 맞았는지는 서버가 정합니다.

0자1줄메모리 256MB (적어만 둡니다)기준 32ms

제출은 로그인 하셔야 됩니다. 공개 케이스로 돌려보는 것은 로그인 없이도 됩니다.

공개 케이스 3개로 돌려보기가 됩니다. 제출하면 숨은 케이스까지 돕니다.

이 문제를 푼 사람

아직 없습니다. 첫 번째가 되실 수 있습니다.