STUDY NOTE · 개념 정리
비트마스크 DP로 푸는 외판원 순회 (BOJ 2098)
Algorithm
N개 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용을 구하는 문제다. N ≤ 16이라 모든 순열(16!)은 불가능하지만, 방문한 도시 집합을 비트로 표현하면 상태 수를 크게 줄일 수 있다.
상태 정의
dp[cur][visited] = 현재 cur에 있고 visited 집합을 방문했을 때, 남은 도시를 모두 돌고 출발점으로 돌아가는 최소 비용.
- 순회는 원형이라 어느 도시에서 시작해도 답이 같다 → 0번 도시에서 시작.
- 상태 수: N × 2N, 전이 N → 전체 O(N² · 2N) ≈ 1,600만.
const int INF = 1e9;
int n, w[16][16], dp[16][1 << 16];
int tsp(int cur, int visited) {
if (visited == (1 << n) - 1) // 모두 방문
return w[cur][0] ? w[cur][0] : INF; // 출발점으로 복귀
int &ret = dp[cur][visited];
if (ret != -1) return ret;
ret = INF;
for (int nxt = 0; nxt < n; nxt++) {
if (visited & (1 << nxt)) continue; // 이미 방문
if (!w[cur][nxt]) continue; // 길 없음
ret = min(ret, w[cur][nxt] + tsp(nxt, visited | (1 << nxt)));
}
return ret;
}
// memset(dp, -1, sizeof dp); cout << tsp(0, 1);
놓치기 쉬운 부분
- 갈 수 없는 경우를 0과 구분해야 한다. 이 문제는 비용 0이 "길 없음"이다.
- 방문했지만 불가능한 상태도 메모해야 한다. INF를 미방문 표시로 같이 쓰면 불가능한 상태를 계속 다시 계산해서 시간 초과가 난다. 그래서 미방문은 -1로 따로 둔다.
1 << 16× 16 × 4바이트 ≈ 4MB라 메모리는 충분하다.
같은 아이디어로 "집합 + 현재 위치"가 상태인 문제(그림 교환 BOJ 1029 등)를 풀 수 있다.