[BOJ/Gold 1] 백준 16991 외판원 순회 3(C++)

문제 링크

https://www.acmicpc.net/problem/16991

 

문제

외판원 순회 문제는 영어로 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까지 허용한다.

 

예제 입력 1

4
1 1
2 2
1 2
2 1

예제 출력 1

4.0

예제 입력 2

4
1 1
5 3
3 1
3 3

예제 출력 2

9.656854249

예제 입력 3

6
30 650
54 330
22 100
99 343
-54 -234
-666 999

예제 출력 3

3091.3804200514593

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

브루트포스로 해결하면 시간이 오래 걸리므로 TSP를 이용해서 해결한다.

먼저 도시 N개의 좌표를 입력받고 비용 행렬을 만든다.

비트마스킹을 이용해서 현재 무슨 도시를 방문했는지를 기록하는데, 도시는 최대 16개까지 등장하므로 비트마스킹 사용이 가능하다.

임의로 1번째 도시에서 출발하기로 한다. 재귀적으로 방문 가능한 다음 도시를 계속 방문해나가면서 무슨 도시를 방문하여 현재 도시까지 왔을 때 드는 비용의 최솟값을 기록한다.

모든 도시를 방문한 경우, 즉 비트마스킹한 수가 (2^N - 1)인 경우 1번째 도시로 돌아올 때 드는 비용을 반환한다.

방문 상태를 최대 2^N * N개까지 기록할 수 있고, 각 상태마다 N개의 도시를 방문하므로 시간복잡도는 O(2^n * n^2)가 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MAX 17
#define INF 1e18
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct POSITION {
	double X, Y;
};

int N;
vector<POSITION> Positions;
double Dist[MAX][MAX], DP[1 << MAX][MAX];
double Answer;

void init() {
	for (int i = 0; i < (1 << MAX); i++) {
		for (int j = 0; j < MAX; j++) {
			DP[i][j] = -1;
		}
	}
}

void input() {
	cin >> N;
	Positions.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> Positions[i].X >> Positions[i].Y;
	}
}

double tsp(int Bitmask, int Now) {
	if (Bitmask == (1 << N) - 1) {
		return Dist[Now][0];
	}
	if (DP[Bitmask][Now] != -1) {
		return DP[Bitmask][Now];
	}

	double MinDist = INF;
	
	for (int i = 0; i < N; i++) {
		if ((Bitmask & (1 << i)) == 0) {
			double NextDist = Dist[Now][i] + tsp(Bitmask | (1 << i), i);
			MinDist = min(MinDist, NextDist);
		}
	}

	return DP[Bitmask][Now] = MinDist;
}

void settings() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			double X1 = Positions[i].X;
			double Y1 = Positions[i].Y;
			double X2 = Positions[j].X;
			double Y2 = Positions[j].Y;
			double NowDist = sqrt((X2 - X1) * (X2 - X1) + (Y2 - Y1) * (Y2 - Y1));
			Dist[i][j] = NowDist;
		}
	}
	Answer = tsp(1, 0);
}

void printAnswer() {
	cout << fixed;
	cout.precision(6);
	cout << Answer << "\n";
}

int main() {
    FASTIO

	init();
	input();
	settings();
	printAnswer();

    return 0;
}