문제 설명
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.
N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.
항상 순회할 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.
0. 들어가며...
외판원 순회(TSP, Traveling Salesman Problem)는 이름만 들으면 거창해 보이지만, 문제의 본질은 비교적 단순하다.
여러 도시를 한 번씩 모두 방문하고 다시 출발점으로 돌아올 때, 그 총 비용이 최소가 되는 경로를 찾는 문제다.
처음 이 문제를 보면 "그래프니까 최단거리 문제 아닌가?"라는 생각이 자연스럽게 든다.
하지만 이 문제는 일반적인 그래프 탐색 문제와는 결이 조금 다르다.
핵심은 현재 위치 하나만으로는 앞으로의 최소 비용을 결정할 수 없다는 점이고, 그 때문에 상태를 다르게 잡아야 한다.
이번 글에서는 외판원 순회를 왜 다른 그래프 탐색으로 풀기 어려운지부터, 왜 비트마스크 DP로 접근해야 하는지, 그리고 코드가 어떤 의미를 가지는지까지 순서대로 정리해보려고 한다.
1. 외판원 순회는 왜 다른 그래프 탐색으로 풀기 어려울까?
MST로는 안 된다
가장 먼저 떠올릴 수 있는 건 MST(최소 신장 트리)다.
어쨌든 모든 정점을 최소 비용으로 연결하는 문제처럼 보이기 때문이다.
하지만 MST는 모든 정점을 최소 비용으로 연결할 뿐이지,
한 사람이 한 경로로 순서대로 방문하는 문제는 아니다.
예를 들어 0번 정점에서 1번, 2번 정점으로 가는 비용이 가장 작다고 해보자.
MST라면 0-1, 0-2 두 간선을 선택할 수 있다.
하지만 외판원 순회에서는 그렇게 “가지를 뻗는” 식으로 갈 수 없다.
우리가 해야 하는 건
0 -> 1 -> 2 -> 00 -> 2 -> 1 -> 0
처럼 하나의 순서로 이동하는 경로를 만드는 것이다.
다익스트라로도 안 된다
그렇다면 다익스트라는 어떨까?
최단거리 문제니까 얼핏 맞아 보일 수도 있다.
하지만 다익스트라는 기본적으로 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘이다.
즉 출발점과 도착점이 주어졌을 때, 그 둘 사이의 최소 비용을 구하는 데 강하다.
반면 외판원 순회는 단순히 "어디서 어디까지 가장 짧게 가느냐"가 아니다.
모든 도시를 한 번씩 다 방문해야 하고, 그 방문 순서 자체가 총 비용을 바꾼다.
즉 이 문제는 “최단거리”라기보다 최적의 방문 순서를 찾아야 하는 문제다.
그래서 다익스트라처럼 현재 위치에서 가장 짧은 경로만 확정해 나가는 방식으로는 해결할 수 없다.
순열 완전탐색은 맞지만 너무 느리다
그럼 가장 정직한 방법은 무엇일까?
모든 도시를 도는 순서를 순열로 만들어 보고, 각 순서의 비용을 계산하는 것이다.
이 방식은 이론상 맞다.
실제로 가능한 모든 경로를 다 확인하니 정답을 놓칠 일도 없다.
하지만 문제는 경우의 수다.
도시가 N개라면 방문 순서는 N!개가 된다.
백준 2098번 기준으로 N은 최대 16인데, 16!은 도저히 완전탐색으로 감당할 수 있는 수준이 아니다.
즉 순열은 논리적으로 맞지만, 시간 복잡도 때문에 사용할 수 없다.
2. 이 문제에서 진짜 중요한 건 무엇일까?
외판원 순회에서 핵심은 “도시를 어떤 순서로 방문하느냐”이다.
어떤 특정 도시까지 오는 비용은,
그 전에 어떤 도시들을 방문했는지에 따라 달라질 수 있다.
예를 들어 현재 3번 도시에 도착했다고 해보자.
0 -> 1 -> 3으로 온 경우0 -> 2 -> 3으로 온 경우
둘 다 현재 위치는 3번 도시지만,
이미 방문한 도시 집합이 다르기 때문에 앞으로의 최소 비용도 달라진다.
즉 이 문제에서는 현재 도시만으로는 상태를 표현할 수 없다.
그런데 여기서 중요한 포인트가 하나 더 있다.
과거에 어떤 순서로 왔는지 전부를 기억할 필요는 없다는 점이다.
앞으로의 최소 비용을 결정하는 데 필요한 정보는 결국 두 가지뿐이다.
지금까지 어떤 도시들을 방문했는가
현재 어느 도시에 있는가
이 두 정보만 같으면, 앞으로 남은 최소 비용은 항상 같다고 볼 수 있다.
그래서 순열처럼 경로 전체를 기억할 필요 없이, 현재 도시 + 방문 집합만 기억하면 된다.
3. 그래서 상태를 어떻게 잡아야 할까?
이 지점에서 비트마스크 DP가 등장한다.
외판원 순회에서는 상태를 다음처럼 둔다.
dp[mask][i] // mask에 해당하는 도시들을 이미 방문했고 현재 마지막 도시가 `i`일 때 필요한 최소 비용여기서 mask란 무엇일까?
"방문한 도시 집합"을 숫자로 관리하기 위해 비트마스킹 기법을 사용한 것이다.
예를 들어 도시가 4개라면,
0001: 0번 도시만 방문
0101: 0번, 2번 도시 방문
1111: 모든 도시 방문
처럼 표현할 수 있다.
4. 점화식은 어떻게 세울까?
현재 상태가 dp[mask][i]라고 하자.
이 상태에서 다음에 할 일은 아직 방문하지 않은 도시 j 하나를 새로 방문하는 것이다.
그러면 새로운 상태는
방문 집합에
j가 추가된nextMask = mask | (1 << j)
현재 마지막 도시는j
가 된다.
즉 전이는 다음처럼 된다.
dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + W[i][j]);현재 상태까지 오는 최소 비용에 i -> j 이동 비용을 더해서,
새 상태의 최소 비용을 갱신하는 것이다.
5. 코드로 보면 어떻게 되는가?
핵심만 설명하자면,
5-1. DP 배열 선언과 초기화
dp = new int[1 << N][N];
for (int i = 0; i < (1 << N); i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}여기서는 모든 상태를 일단 "아직 갈 수 없음"으로 초기화한다.
dp[mask][i]는 mask 상태에서 마지막 도시가 i인 최소 비용인데,
초기에는 아무 상태도 계산되지 않았으니 모두 무한대로 두는 것이다.
5-2. 시작점 초기화
dp[1][0] = 0;외판원 순회는 시작점을 아무 도시로 잡아도 된다.
예를 들어 2 -> 3 -> 1 -> 0 -> 2라는 순회는
0 -> 2 -> 3 -> 1 -> 0와 같은 순회이기 때문이다.
그래서 구현에서는 편의상 시작점을 0번으로 고정해도 정답이 변하지 않는다.
5-3. 상태 전이
for (int mask = 0; mask < (1 << N); mask++) {
for (int i = 0; i < N; i++) {
if (dp[mask][i] == Integer.MAX_VALUE) continue;
for (int j = 0; j < N; j++) {
if ((mask & (1 << j)) != 0) continue;
if (W[i][j] == 0) continue;
int nextMask = mask | (1 << j);
dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + W[i][j]);
}
}
}이 부분이 외판원 순회의 핵심이다.
먼저 mask를 하나 고른다. (이건 현재까지 방문한 도시 집합이다.)
그 다음 i를 고른다. (이건 현재 마지막 도시다.)
즉 dp[mask][i]가 의미 있는 상태라면,
아직 방문하지 않은 다음 도시 j를 하나 골라 이동할 수 있다.
여기서
(mask & (1 << j)) != 0는 j가 이미 방문된 도시인지 확인하는 코드이고,
int nextMask = mask | (1 << j);는 j를 새로 방문 집합에 추가한 상태를 만드는 코드다.
즉 이 전이 전체는 "현재 상태에서 아직 안 간 도시 하나를 새로 방문하면서 최소 비용을 갱신한다"는 뜻이다.
5-4. 마지막으로 시작점으로 복귀
ans = Integer.MAX_VALUE;
for (int i = 1; i < N; i++) {
if (dp[(1 << N) - 1][i] == Integer.MAX_VALUE) continue;
if (W[i][0] == 0) continue;
ans = Math.min(ans, dp[(1 << N) - 1][i] + W[i][0]);
}(1 << N) - 1은 모든 도시를 방문한 상태다.
즉 dp[(1 << N) - 1][i]는 모든 도시를 방문했고 마지막 도시가 i일 때의 최소 비용이다.
하지만 외판원 순회는 여기서 끝나는 게 아니라, 다시 시작 도시 0으로 돌아와야 한다.
그래서 마지막 도시 i에서 0으로 돌아가는 비용 W[i][0]을 더해주고, 그중 가장 작은 값을 최종 답으로 선택한다.
6. 시간복잡도
이 풀이의 시간복잡도는 O(2^N * N^2)이다.
이유는 다음과 같다.
먼저 방문 집합 mask의 경우의 수가 2^N개 있다.
각 mask마다 현재 마지막 도시 i를 하나 잡아야 하므로 N번 확인한다.
그리고 그 상태에서 다음에 방문할 도시 j를 다시 N개 순회하며 전이한다.
즉 전체 반복은 대략
2^N * N * N
이 되는 것을 확인할 수 있다.
7. 마무리
이 문제에서 중요한 건 경로 전체를 기억하는 것이 아니라,
이미 방문한 도시 집합과 현재 도시만 기억하면 충분하다는 점이다.
이 한 가지를 이해하면 왜 dp[mask][i]가 필요한지, 왜 비트마스크를 쓰는지, 왜 점화식이 저렇게 나오는지도 자연스럽게 따라온다.
외판원 순회의 핵심을 한 문장으로 정리하면서 마무리하겠다.
방문 집합과 현재 도시를 상태로 두고, 아직 안 간 도시를 하나씩 추가하며 최소 비용을 갱신하는 비트마스크 DP 문제다.
