문제
N개의 도시를 모두 한 번씩 방문하고 출발 도시로 돌아오는 최소 비용을 구하는 문제다. 전형적인 TSP(Traveling Salesman Problem)이다.
모든 방문 순서를 직접 만들면 경우의 수가 N!개라 N=16에서도 감당하기 어렵다. 하지만 경로의 과거 순서 전체가 아니라 현재 도시와 이미 방문한 도시 집합만 알면 다음 선택을 계산할 수 있다.
핵심 아이디어
- N이 최대 16이므로 정수의 각 비트를 도시 하나에 대응시킨다. 이런 표현을 비트마스크라고 한다.
dp[cur][visit]= 현재cur도시에 있고, 방문 상태가visit일 때 남은 도시를 모두 방문하고 돌아오는 최소 비용이다.- 모든 도시를 방문한 상태(
visit == (1 << n) - 1)에서 출발지로 돌아갈 수 있으면 해당 비용을 반환한다. - 출발 도시를 0번으로 고정해도 되는 이유는 순환 경로이기 때문이다.
도시가 4개일 때 visit = 0101₂라면 0번과 2번 도시를 방문했다는 뜻이다. 3번 도시를 새로 방문한 상태는 visit | (1 << 3), 즉 1101₂가 된다. 반대로 visit & (1 << 2)가 0이 아니면 2번 도시는 이미 방문한 것이다.
풀이
#define INF 987654321
#include <iostream>
using namespace std;
int n;
int w[16][16];
int dist[16][1 << 16] = {0,};
int tsp(int cur, int visit) {
if (visit == (1 << n) - 1) {
if (w[cur][0] == 0) return INF;
return w[cur][0];
}
int& ret = dist[cur][visit];
if (ret != 0) return ret;
ret = INF;
for (int next = 0; next < n; next++) {
if (visit & (1 << next)) continue;
if (w[cur][next] == 0) continue;
int t = tsp(next, visit | (1 << next)) + w[cur][next];
ret = min(ret, t);
}
return ret;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> w[i][j];
}
}
cout << tsp(0, 1) << endl;
return 0;
}
주요 포인트
int& ret = dist[cur][visit]는 현재 상태의 저장 공간에 별명을 붙인 것이다. 계산한 값을 그대로 메모이제이션 배열에 남길 수 있다.w[cur][next] == 0이면 해당 경로가 없는 것으로 처리한다.- 초기 호출
tsp(0, 1)에서1은 0번 도시를 이미 방문한 상태를 뜻한다.
복잡도
- 시간: O(N^2 × 2^N)
- 공간: O(N × 2^N)
순서 전체를 저장하지 않고 현재 도시 + 방문한 도시 집합만 남기면 N! 탐색을 O(N² × 2^N)으로 줄일 수 있다.
댓글