방과후
ALGORITHM NOTE약 2분

BOJ 16991 - 외판원 순회 3

담백한 외판원 순회 문제

#algorithm#boj#gold#dp#bitmask#bitmask-dp#tsp
아카이브로 돌아가기

문제 링크

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 모든 도시 사이에는 길이 있다. 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

도시 A에서 도시 B로 가는 비용은 두 도시 사이의 거리와 같다. 한 도시 A의 좌표가 (xA, yA), B의 좌표가 (xB, yB)라고 한다면, 두 도시의 거리는 √((xB-xA)^2 + (yB-yA)^2)와 같다.

도시의 수 N과 모든 도시의 위치가 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 도시의 좌표 x, y가 주어진다. 모든 좌표는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 두 도시의 위치가 같은 경우는 없다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다. 절대/상대 오차는 10^-6까지 허용한다.

풀이

모든 도시를 한 번씩 방문하고 다시 시작점으로 돌아와야 하므로, 현재까지 방문한 도시 집합과 현재 위치를 함께 상태로 들고 가는 비트마스크 DP가 잘 맞는다. 단순 순열 완전탐색으로는 경우의 수가 너무 크기 때문이다.

코드에서는 solve(cur, bitmask)를 현재 cur 도시에 있고, bitmask에 표시된 도시들을 이미 방문했을 때 남은 최소 비용으로 둔다. 모든 도시를 방문한 상태라면 시작점으로 돌아가는 비용을 그대로 반환하고, 아니라면 아직 방문하지 않은 다음 도시를 모두 시도하면서 최소값을 갱신한다.

도시 사이 거리는 좌표로부터 직접 계산하므로 별도의 그래프 입력이 없어도 된다. 핵심은 같은 방문 집합과 같은 현재 위치 조합은 언제 도달했든 남은 최소 비용이 같다는 점이고, 이 성질 덕분에 메모이제이션이 정확하게 작동한다.

코드

cpp
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 17
#define INF 10e16
using namespace std;
 
int n;
vector<pair<double, double>> cities;
double dp[MAX][1 << MAX];
 
double getDistance(double x1, double y1, double x2, double y2) {
	return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
 
double solve(int cur, int bitmask) {
	if (bitmask == (1 << n) - 1)
		return getDistance(cities[cur].first, cities[cur].second, cities[0].first, cities[0].second);	// 시작 지점으로 돌아가기
 
	if (dp[cur][bitmask] != -1.0)
		return dp[cur][bitmask];	// 메모리제이션
 
	dp[cur][bitmask] = INF;	// 최댓값으로 초기화 (초기값)
 
	for (int i = 0; i < n; i++) {
		if ((bitmask & (1 << i)) == 0 && cur != i) {
			dp[cur][bitmask] = min(dp[cur][bitmask], solve(i, bitmask | (1 << i)) + 
			getDistance(cities[cur].first, cities[cur].second, cities[i].first, cities[i].second));
		}
	}
 
	return dp[cur][bitmask];
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	
	for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << n); j++) {
            dp[i][j] = -1.0;
        }
    }
 
	for (int i = 0; i < n; i++) {
		double x, y;
		cin >> x >> y;
		cities.push_back(make_pair(x, y));
	}
	
	// 소수점 6자리까지 표현
	cout << fixed;
	cout.precision(6);
 
	cout << solve(0, 1) << '\n';
	return 0;
}

복잡도

  • 시간 복잡도: 상태 수 기준 O(N2⋅2N)O(N^2 \cdot 2^N)
  • 공간 복잡도: O(N⋅2N)O(N \cdot 2^N)

마무리

외판원 순회는 순서를 전부 세기 시작하면 금방 폭발한다. 방문 집합과 현재 위치만 상태로 남기면 같은 부분 문제를 재사용할 수 있어 비트마스크 DP 구조가 선명하게 드러난다.