문제 52
외판원 순회 문제
$1$번부터 $N$번까지 번호가 붙은 도시가 있다.
서로 다른 두 도시 사이를 이동할 때 필요한 비용이 주어진다.
$1$번 도시에서 출발하여 모든 도시를 정확히 한 번씩 방문한 뒤 다시 $1$번 도시로 돌아올 때 필요한 비용의 최솟값을 구하라.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 17)$
두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $N$개의 정수가 공백으로 구분되어 주어진다. 이 중 $i$번째 줄의 $j$번째 정수 $C_{i,j}$는 $i$번 도시에서 $j$번 도시로 이동할 때 필요한 비용이다.
$i=j$이면 $C_{i,j}=0$이고, $i \neq j$이면 $1 \le C_{i,j} \le 10^9$이다.
출력
필요한 비용의 최솟값을 출력한다.
예제 입력 1
4 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0
예제 출력 1
35
예제 입력 2
1 0
예제 출력 2
0
공식 해설
$N\le17$이므로 방문 순열 전체를 열거하기보다는 $2^N$개의 방문 집합을 상태로 사용할 수 있다.
방문한 도시들의 집합과 현재 도시가 같으면 남은 선택도 같다. 이전 방문 순서를 모두 기억할 필요 없이 이 두 정보만 상태로 둔다.
$D(S,v)$를 집합 $S$의 도시들을 방문하고 $v$에 있을 때, 나머지 도시를 모두 방문한 뒤 $1$번으로 돌아가는 최소 추가 비용으로 정의한다. 다음에 방문할 도시 $u$를 고르면
\[
D(S,v)=\min_{u\notin S}\bigl(C_{v,u}+D(S\cup\{u\},u)\bigr)
\]
이다. 모든 도시를 방문했다면 남은 비용은 $C_{v,1}$이다.
어떤 순회도 다음 도시 하나를 선택하는 것으로 시작하고, 위 식은 그 모든 선택을 포함한다. 집합 크기가 늘어나는 방향으로만 전이하므로 메모이제이션이나 비트마스크 DP로 각 상태를 한 번씩 계산하면 된다.
답은 $D(\{1\},1)$이다. $N=1$이면 기저 상태에서 $C_{1,1}=0$을 얻는다. 순회 비용은 최대 $N\cdot10^9$이므로 경로 전체의 합을 고려해야 한다.
상태가 $O(N2^N)$개이고 상태마다 최대 $N$개 전이를 확인하므로 시간복잡도는 $O(N^2 2^N)$, 공간복잡도는 $O(N2^N)$이다.
구현 · 언어별 풀이
C++ 구현
방문 집합은 int 비트마스크로 나타내고 비용 표는 long long으로 저장한다. 미계산 상태는 $-1$, 비교용 무한대는 충분히 큰 양수로 구분한다. $1$번 도시를 비트 $0$에 대응시키면 시작 상태는 (1, 0)이다. 간선 비용이 비대칭일 수 있으므로 방향을 그대로 읽는다.
C 구현
dp[mask*N+u]를 long long 평탄 배열로 두고 미계산 표식은 -1로 한다. 최대 비용은 $17 \cdot 10^9$이므로 int는 부족하다. 재귀 깊이는 $N$ 이하이며 모든 도시를 방문하면 시작 도시로 돌아가는 비용을 더한다.
Python 구현
상태 수가 $N \cdot 2^N$이므로 tuple 키 dict 캐시는 큰 객체 비용을 낸다. array('q') 같은 평탄 64비트 배열에 메모이제이션한다. 재귀 깊이는 최대 17이라 일반 재귀로 충분하며 N=1의 답도 0이다.
Java 구현
long[] dp를 mask*N+u로 평탄화한다. -1을 미계산 표식으로 쓰고 전체 방문 시 C[u][0]을 반환한다. 비용 행렬 원소는 int여도 dp와 덧셈은 long으로 계산한다.
Rust 구현
Vec<i64>를 평탄 dp로 사용하고 -1로 초기화한다. mask는 usize이며 1usize << N으로 상태 크기를 구한다. 재귀 호출 전에 필요한 비용을 복사하면 dp의 가변 borrow를 오래 유지하지 않는다.
JavaScript 구현
방문 마스크는 최대 $17$비트이므로 1 << v와 비트 연산을 사용해도 부호나 정밀도 문제가 없다. 반면 한 경로 비용은 $17\cdot10^9$까지 커져 $32$비트 정수 범위를 넘으므로 DP는 Float64Array에 둔다. 이 범위는 Number의 안전 정수 범위 안이다.
상태를 mask * n + v로 펼치면 많은 작은 배열을 만들 필요가 없다. 비용은 음수가 아니므로 메모이제이션 배열을 -1로 채워 아직 계산하지 않은 상태와 구분할 수 있다. 재귀 깊이는 방문 도시 수인 $17$ 이하라 깊은 그래프 DFS와 달리 호출 스택 문제가 없다.
마스크에 모든 도시가 들어 있으면 $v$에서 시작 도시로 돌아가는 비용을 반환한다. $N=1$의 대각선 비용은 $0$이므로 별도 임의 비용을 더하지 않는다. 시간은 $O(N^2 2^N)$, DP 공간은 $O(N2^N)$이다.