[백준 16991] 외판원 순회 3

문제 링크 : 16991번: 외판원 순회 3 (acmicpc.net)

16991번: 외판원 순회 3

문제

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

---

비트마스킹 문제이다.

자동장치이론에서 배웠던 내용이며(traveling salesman, min set cover (tistory.com)) 이를 문제로 해결하는 것은 처음이다. 

외판원 순회 문제(TSP)는 NP 문제이다. (polynomial time 으로 해결할 수 없으며 exponential time 으로 해결 가능)

따라서 N의 범위가 굉장히 작은 것을 캐치할 수 있다.

우선, 문제 해결을 위한 double 형 2차원 배열 point, W, cost 를 선언하였다.

 

double point[17][2]; // (xi, yi) 좌표
double W[17][17]; // i ~> j 의 가중치
double cost[17][1 << 16]; // 비트마스킹을 위한 배열

 

※ 문제 접근 방법

① (\(x_{i}\), \(y_{i}\)) 가 주어졌으므로, 한 정점에서 다른 정점으로 이동하는데의 가중치를 정해야 한다. (1 ≤ i ≤ N)

가중치 W 를 세팅하는 함수는 다음과 같다.

 

void set_weight() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			W[i][j] = sqrt(pow(point[i][0] - point[j][0], 2) 
				+ pow(point[i][1] - point[j][1], 2));
		}
	}
}

 

② cost 배열을 INF 로 모두 초기화한다. (임의의 정점에서 아직 해결하지 못한것을 표시하기 위함)

그리고 다음과 같이 현재 정점과 비트를 활용하여 문제를 해결한다.

 

double dfs(int cur_node, int cur_bit) {
	// 모든 정점을 다 방문하게 된 경우
    // 예를 들어 N = 4 일때, 1111 인 경우 모두 방문하였음
	if (cur_bit == (1 << N) - 1) {
    	// 원점(1)으로 돌아갈 수 없는 경우 (cur_node ~> 1 no)
		if (W[cur_node][1] == 0) return INF;
        // 원점(1)으로 돌아갈 수 있는 경우 (cur_node ~> 1 ok)
		return W[cur_node][1];
	}

	// 현재 정점으로 이동한 경로가 이전과 동일한 경우 
	if (cost[cur_node][cur_bit] != INF)
		return cost[cur_node][cur_bit];

	// 비트마스킹을 하는 작업
	for (int next_node = 1; next_node <= N; next_node++) {
		// 현재 노드에서 다음 노드로 이동할 수 없는 경우
        if (!W[cur_node][next_node]) continue;
        // 현재 노드에서 다음 노드로 이동하려고 하지만 이미 방문된 경우 
        // ex) N = 4, cur_bit = 0111, cur_node = 2, next_node = 3 일 때 이미 방문된 경우
		if((cur_bit & (1 << (next_node - 1))) == (1 << (next_node - 1))) continue;
        
        // cur_node ~> next_node 로의 가중치를 더하고 비트마스킹하여 인자값을 넘겨줌
		cost[cur_node][cur_bit] = min(cost[cur_node][cur_bit],
			W[cur_node][next_node] + dfs(next_node, cur_bit | (1 << (next_node - 1))));
	}

	// 현재 정점과 bit를 고려한 비용을 반환
	return cost[cur_node][cur_bit];
}

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N;
double point[17][2];
double W[17][17];
double cost[17][1 << 16];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> point[i][0] >> point[i][1];
	}
}

void set_weight() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			W[i][j] = sqrt(pow(point[i][0] - point[j][0], 2) 
				+ pow(point[i][1] - point[j][1], 2));
		}
	}
}

void init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= (1 << N) - 1; j++) {
			cost[i][j] = INF;
		}
	}
}

double dfs(int cur_node, int cur_bit) {
	if (cur_bit == (1 << N) - 1) {
		if (W[cur_node][1] == 0) return INF;
		return W[cur_node][1];
	}

	if (cost[cur_node][cur_bit] != INF)
		return cost[cur_node][cur_bit];

	for (int next_node = 1; next_node <= N; next_node++) {
		if (!W[cur_node][next_node]) continue;
		if((cur_bit & (1 << (next_node - 1))) == (1 << (next_node - 1))) continue;
		cost[cur_node][cur_bit] = min(cost[cur_node][cur_bit],
			W[cur_node][next_node] + dfs(next_node, cur_bit | (1 << (next_node - 1))));
	}

	return cost[cur_node][cur_bit];
}

void solution() {
	set_weight();
	init();
	double result = dfs(1, 1);
	printf("%.6f", result);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution();

	return 0;
}