외판원 순회 문제
외판원 순회 문제란 도시들과 도시 간 이동 비용이 주어졌을 때, 외판원이 각 도시를 한 번씩 방문하고 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다.
외판원 순회 문제는 아직 다항 시간 내에 해결할 수 있는 알고리즘이 발견되지 않았다.
브루트포싱으로는 무려 $O(N!)$의 시간이 걸리며, 오늘 소개할 DP를 이용한 방법으로는 $O(N^22^N)$의 시간이 걸린다.
어떻게 해결할까?
1. 완전 탐색 - $O(N!)$
외판원이 도시를 방문하는 순서를 모두 구한 후, 최소 비용을 찾는 방법이다.
이는 $N$개의 도시를 나열하는 모든 경우를 탐색하는 것으로 $O(N!)$의 시간이 걸린다.
2. 다이나믹 프로그래밍 - $O(N^22^N)$
완전 탐색에서는 이미 계산한 경로의 최소 비용을 중복 계산하게 되는데, 메모이제이션을 적용하면 이 시간을 줄일 수 있다.
메모이제이션용(기록용) 배열 $DP$를 만들어 상황별 최소 비용을 저장해보자.
여기서 "상황"은 "지금까지 방문한 도시들"과 "현재 외판원이 있는 도시"를 의미한다.
따라서 $DP$를 이차원 배열로 만들어 아래와 같이 정의할 수 있겠다.
$DP[i][visited]$ = 현재 방문 상태가 $visited$이고, i번 도시에 있을 때,
남은 도시들을 방문한 후 출발 도시로 돌아오는 최소 비용.
이를 구현하기 위해서는 방문 상태를 숫자를 표현해야 하는데, 이는 비트마스킹을 이용하면 된다.
이진수의 각 자리수를 도시별 방문 여부로 두고 1이면 방문한 곳, 0이면 방문하지 않은 곳으로 생각하는 것이다.
3. 더 빠른 방법?
외판원 순회는 NP-완전 문제로, 다항 시간 내에 해결할 수 있는 알고리즘은 발견되지 않았다.
DP가 아닌 분기 한정법으로도 해결할 수 있으나, 마찬가지로 지수 시간이 걸린다.
구현해보기(C++)
사전 준비: 외판원은 어느 도시에서 출발해야 할까?
외판원 문제는 임의의 한 도시에서 출발해 모든 도시를 거쳐 해당 도시로 다시 돌아오는 최소 비용을 구하는 문제다.
얼핏 보면 출발 도시에 따라 비용이 달라질 것 같지만, 그렇지 않다.
모든 도시를 순회할 수 있는 경로가 있다면, 어느 도시에서 출발하든 그 경로는 바뀌지 않는다. 그저 방문하는 순서만 달라지는 것이다.
또한 특정 도시에서 출발해 순회할 수 있는 경로가 없다면, 다른 모든 도시에서 출발해도 경로는 존재하지 않는다.
따라서 외판원 순회 문제를 해결할 때 어느 도시에서부터 출발하든 아무런 상관이 없다.
DFS를 이용해 구현해보기
DFS와 DP를 이용해 아래와 같이 TSP를 해결할 수 있다. 아래 코드는 백준 2098번의 해답이기도 하다.
#include <bits/stdc++.h>
#define MAX 1e8
using namespace std;
int n;
int arr[16][16];
int dp[16][1 << 16] = { 0 };
int tsp(int index, int visited) {
// 이미 모두 방문한 경우
if (visited == (1 << n) - 1) {
// 0번 도시까지의 거리 리턴. 못가면 MAX 리턴.
return arr[index][0] == 0 ? MAX : arr[index][0];
}
// 이미 계산된 값이 있으면 해당 값 리턴 (메모이제이션)
if (dp[index][visited] > 0) {
return dp[index][visited];
}
dp[index][visited] = MAX;
for (int i = 0; i < n; i++) {
if (visited & (1 << i)) continue; // 이미 방문
if (arr[index][i] == 0) continue; // 경로 없음
dp[index][visited] = min(dp[index][visited], tsp(i, visited | (1 << i)) + arr[index][i]);
}
return dp[index][visited];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
int answer = tsp(0, 1); // 0번 도시에서 출발
cout << (answer == MAX ? -1 : answer); // MAX면 순회 불가이므로 -1 출력
}
위 코드는 0번 도시에서 출발해 DFS로 경로를 탐색, 각 상황의 최소 비용을 $DP$ 배열에 저장해나간다.
최소 비용을 보다 쉽게 계산하기 위해 아예 접근이 불가한 경로의 경우 $MAX$라는 비용을 부여하였다.
관련 문제 (BOJ)
사실 외판원 순회를 응용하는 문제는 그렇게 많지 않다.
정점을 모두 방문하되 한 번씩만 방문 후 다시 되돌아와야 한다는 조건(없으면 MST 활용)이 있고 $N$이 유난히 작다면 TSP를 적용할 수 있는지 살펴보자.
관련 문제는 여기서 확인 가능하다.
