문제
N개의 도시를 모두 정확히 한 번씩 방문하고 출발 도시로 돌아오는 경로 중 비용이 가장 작은 경로의 비용을 구한다. 이것이 외판원 순회 문제(TSP, Travelling Salesman Problem)이다. 이동이 불가능한 경우(비용 0)에는 해당 경로를 선택할 수 없다.
입력
- 첫째 줄: 도시의 수 N (2 이상 16 이하)
- 이후 N개의 줄: N×N 비용 행렬 (0이면 이동 불가)
출력
- 모든 도시를 순회하는 최소 비용
예제
| 입력 | 출력 |
|---|---|
4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0 | 80 |
풀이
비트마스크 DP를 사용하여 현재 도시와 방문한 도시 집합을 상태로 메모이제이션하여 해결하는 전형적인 TSP 풀이법이다.
dp[n][visit]을 "현재 도시가 n이고, 방문한 도시의 집합이 visit일 때의 최소 비용"으로 정의한다.- 초기 호출:
TSP(0, 1)— 도시 0에서 출발, 0번 도시 방문 표시 (비트 1) - 모든 도시를 방문했으면 (
visit == (1 << N) - 1), 출발 도시(0)로 돌아가는 비용을 반환한다. - 방문하지 않은 도시 중 이동 가능한 도시로 재귀 호출하며 최솟값을 갱신한다.
- 계산된 값은
dp[n][visit]에 저장해 중복 계산을 방지한다.
핵심 아이디어: N이 최대 16이므로 방문 상태를 비트마스크(정수 하나)로 표현할 수 있다. 상태 공간이 N × 2^N이므로 전체 경우의 수를 단순 재귀로 탐색하는 대신 메모이제이션으로 최적화한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day76BOJ2098외판원순회TSP {
static final int INF = 16 * 1_000_000;
static int N;
static int[][] arr;
static Integer[][] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
dp = new Integer[N][(1 << N) - 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(TSP(0, 1));
br.close();
}
private static int TSP(int n, int visit) {
if (visit == (1 << N) - 1)
return arr[n][0] == 0 ? INF : arr[n][0];
if (dp[n][visit] != null)
return dp[n][visit];
dp[n][visit] = INF;
for (int i = 0; i < N; i++) {
// print(dp);
if (arr[n][i] == 0 || (visit & (1 << i)) > 0)
continue;
dp[n][visit] = Math.min(dp[n][visit], TSP(i, (visit | 1 << i)) + arr[n][i]);
}
return dp[n][visit];
}
static int pcnt = 1;
private static void print(Integer[][] a) {
StringBuilder tt = new StringBuilder();
tt.append("===== " + pcnt++ + "번째 =====\n");
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
tt.append((dp[i][j] != null) ? dp[i][j] : "n").append("\t");
}
tt.append("\n");
}
System.out.println(tt.toString());
}
}복잡도
- 시간: O(N × 2^N) — 상태 공간의 크기
- 공간: O(N × 2^N) — dp 테이블 크기