이번에는 백준 2098번 외판원 순회 문제를 풀어보았습니다.
문제를 처음 봤을 때 모든 경로를 완전탐색하면 경우의 수가 너무 많아 시간 내에 해결할 수 없다고 생각했습니다.
하지만 현재 위치와 지금까지 방문한 도시만 같다면, 이후에 방문해야 하는 도시들의 최소 비용은 항상 같다는 점을 이용하여 DP와 비트마스킹으로 해결하였습니다.
문제 설명
N개의 도시가 주어집니다.
한 도시에서 출발하여 모든 도시를 정확히 한 번씩 방문한 뒤 다시 출발 도시로 돌아와야 합니다.
가능한 모든 경로 중 최소 비용을 구하는 문제입니다.
풀이 아이디어
현재 상태를
- 현재 위치한 도시
- 지금까지 방문한 도시 집합
으로 정의하였습니다.
현재 위치와 방문한 도시가 같다면 이후에 남은 도시들을 모두 방문하는 최소 비용은 항상 같습니다.
따라서 같은 상태는 한 번만 계산하도록 DP를 사용하였습니다.
방문한 도시는 비트마스킹으로 관리하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int dist[16][16];
int N;
int dp[16][1 << 16];
int tsp(int here, int visited) {
if (visited == (1 << N)-1)
return dist[here][0] ? dist[here][0] : INT_MAX;
int &ret = dp[here][visited];
if (ret != -1)
return ret;
ret = INT_MAX;
for (int i=0; i<N; i++) {
if (visited & (1 << i)) continue;
if (!dist[here][i]) continue;
ret = min(ret,
tsp(i, visited | (1 << i)) + dist[here][i]);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cin >> dist[i][j];
}
}
memset(dp, -1, sizeof(dp));
cout << tsp(0,1) << '\n';
return 0;
}풀이 흐름
- 도시 간 이동 비용을 입력받습니다.
- 현재 위치와 방문한 도시를 상태로 정의합니다.
- 아직 방문하지 않은 도시를 하나씩 선택합니다.
- 모든 도시를 방문하면 시작 도시로 돌아갑니다.
- 같은 상태는 DP를 이용하여 재사용합니다.
- 최소 비용을 출력합니다.
구현 포인트
1. 방문 도시를 비트마스킹으로 관리
방문한 도시를 하나의 정수로 관리하였습니다.
visited예를 들어
001011이라면
0, 1, 3번 도시 방문을 의미합니다.
모든 도시를 방문한 상태는
(1 << N) - 1로 확인하였습니다.
2. DP 상태 정의
DP는
dp[현재 도시][방문 집합]형태로 사용하였습니다.
dp[here][visited]의 의미는
현재 도시가 here이고, visited 상태일 때 남은 도시를 모두 방문하고 시작점으로 돌아가는 최소 비용입니다.
3. 메모이제이션
이미 계산한 상태라면 다시 계산하지 않고 바로 반환하였습니다.
if (ret != -1)
return ret;동일한 상태는 항상 같은 결과를 가지므로 메모이제이션이 가능합니다.
4. 다음 도시 선택
아직 방문하지 않은 도시만 선택하였습니다.
if (visited & (1 << i))
continue;또한 길이 없는 경우는 제외하였습니다.
if (!dist[here][i])
continue;이후 다음 상태의 최소 비용을 계산하였습니다.
ret = min(ret,
tsp(i, visited | (1 << i)) + dist[here][i]);5. 모든 도시를 방문한 경우
모든 도시를 방문했다면 시작 도시로 돌아가야 합니다.
if (visited == (1 << N)-1)돌아가는 길이 존재하면 해당 비용을 반환하고,
return dist[here][0];길이 존재하지 않는 경우에는 매우 큰 값을 반환하였습니다.
return INT_MAX;6. 상태가 같은 경우는 항상 같은 결과
이 문제의 핵심은
A → B → C → D
A → C → B → D처럼 방문 순서는 다르더라도,
현재 상태가
현재 도시 : D
방문 집합 : {A, B, C, D}으로 같다면 이후 남은 도시를 방문하는 최소 비용은 항상 같다는 점입니다.
그래서
dp[현재 도시][방문 집합]만으로 모든 상태를 메모이제이션할 수 있으며,
이를 통해 완전탐색보다 훨씬 빠르게 문제를 해결할 수 있었습니다.
