연습문제

더블! 산타 외판원 순회

난이도
Lv. 4
제출
13 명
참가자
4 명
정답률
10.00 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C 1초 1024MB
Java 1초 1024MB
Python 2초 1024MB
C++ 1초 1024MB
JavaScript 2초 1024MB

두 명의 산타가 n개의 도시에 선물을 주려고 합니다. 두 산타는 서로 방문하는 도시가 겹치지 않게 방문하려 하고, 모든 도시는 다 방문되어야만 합니다. 또한 각 산타가 방문하는 방식은 외판원 순회(TSP)와 같아서, 임의의 시작 도시로부터 이동한 뒤에는 다시 시작 도시로 돌아와야만 합니다. 각 산타는 최소 2개 이상의 도시를 방문해야만 한다 했을 때, 모든 도시를 방문하기 위해 두 산타가 이동해야 하는 이동거리의 합 중 가능한 최솟값을 구하는 프로그램을 작성해보세요.





본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

  • 4 ≤ n ≤ 14
  • 0 ≤ cost[i][j] ≤ 1,000,000

입력형식

첫 번째 줄에는 도시의 수를 나타내는 n이 주어집니다.

두 번째 줄 부터는 n개의 줄에 걸쳐서 비용 행렬이 주어집니다. cost[i][j] 는 도시 i에서 j로 가기 위한 비용을 나타내며, 0인 경우 이동이 불가능함을 뜻합니다.

출력형식

두 산타가 모든 도시를 방문하기 위해 필요한 이동거리의 합 중 최솟값을 출력합니다. 불가능한 경우는 없다고 가정해도 좋습니다.

입력예제1

4
0 10 10 10
10 0 7 10
10 8 0 10
10 10 10 0
출력예제1

35

예제 1번의 경우 첫 번째 산타는 (2, 3, 2) 순으로, 두 번째 산타는 (1, 4, 1)순으로 이동하게 되면 이동 거리의 합은 7 + 8 + 10 + 10 = 35로 최소가 됩니다.

입력예제2

5
0 10 10 6 10
10 0 7 10 5
10 6 0 10 5
10 10 6 0 10
10 4 10 10 0
출력예제2

31

예제 2번의 경우 첫 번째 산타는 (1, 4, 3, 1) 순으로, 두 번째 산타는 (2, 5, 2)순으로 이동하게 되면 이동 거리의 합은 6 + 6 + 10 + 5 + 4 = 31로 최소가 됩니다.

목록