// https://www.acmicpc.net/problem/2098 /* 해설 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다. 각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자. N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. 출력 첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다. --- TSP 연습문제 */ /* 입력 4 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 */ /* 출력 35 * */ import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[][] dist = new int[N][N]; for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j ++) { dist[i][j] = Integer.parseInt(st.nextToken()); } } // System.out.println(Arrays.deepToString(dist)); int maxRoute = (1 << N); long[][][] dp = new long[N][N][maxRoute]; for (int i = 0; i < N; i ++) { for (int j = 0; j < N; j ++) { Arrays.fill(dp[i][j], Long.MAX_VALUE); } } for (int i = 0; i < N; i ++) { for (int j = 0; j < N; j ++) { if (dist[i][j] == 0) continue; dp[i][j][(1 << j)] = Math.min(dp[i][j][(1 << j)], (long) dist[i][j]); } } // System.out.println(Integer.toBinaryString(maxRoute-1)); long ans = Long.MAX_VALUE; for (int start = 0; start < N; start ++) { // 16 for (int from = 0; from < N; from++) { // 16 for (int to = 0; to < N; to++) { // 16 for (int route = 0; route < maxRoute; route++) { // 60000 if (dist[from][to] == 0) continue; if (dp[start][from][route] != Long.MAX_VALUE) { if (((route & (1 << to)) != (1 << to)) && ((route & (1 << from)) == (1 << from))) { dp[start][to][(route | (1 << to))] = Math.min(dp[start][to][route | (1 << to)], dp[start][from][route] + (long) dist[from][to]); if (start == to && (route | (1 << to)) == maxRoute-1) { ans = Math.min(ans, dp[start][to][(route | (1 << to))]); } } } } } } } // System.out.println(Arrays.deepToString(dp)); System.out.println(ans); } } /* * */

제출 #139490

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: