[BOJ 24519 // C++] Bottleneck Travelling Salesman Problem (Large)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24519번 문제인 Bottleneck Travelling Salesman Problem (Large)이다.
문제는 아래 링크를 확인하자.

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

24519번: Bottleneck Travelling Salesman Problem (Large)

TSP 문제는 다양한 풀이가 잘 알려져있는 문제이다. 여기서는 비트최적화 DP로 문제를 해결해보자.

 

최적화를 위해 도시번호는 0-based index를 이용하겠다.

 

지금까지 방문한 도시들의 집합 S와 현재 방문중인 도시 C의 순서쌍 (S,C)를 하나의 노드로 생각하자. 그리고 0번 도시에소 출발해 S의 도시들을 전부 방문한 상태로 C 도시에 머무를 때 (이 순간까지 사용한 에지의 최장거리의 최솟값)을 dp((S,C))로 쓰기로 하자.

 

dp((S,C))는 "dp((S에서 도시 C이 빠진 집합 S', S'의 원소 C')) 와 (C'에서 C까지의 거리)의 최댓값"들의 최솟값으로 나타낼 수 있다는 점을 관찰해 dp를 진행해보자.

 

여기서 집합 S는 도시의 수가 충분히 적다면 비트를 이용해 하나의 정수로 표현이 가능하다는 점을 적극 이용하자.

 

아래는 제출한 소스코드이다.

#define MP(x,y) make_pair(x,y)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int dp[262144][18];
int old[262144][18];
bool visited[262144];
vector<pair<int, int>> G[19];

void bfs() {
	dp[1][0] = 1;
	queue<int> que;
	que.push(1);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (int s = 0; s < N; s++) {
			if (dp[cur][s] == 0) continue;
			for (auto& p : G[s]) {
				int e = p.first, c = p.second;
				if (cur & (1 << e)) continue;
				int nxt = cur | (1 << e);
				int val = max(dp[cur][s], c);
				if (dp[nxt][e]) {
					if (val < dp[nxt][e]) {
						dp[nxt][e] = val;
						old[nxt][e] = s;
					}
				}
				else {
					dp[nxt][e] = val;
					old[nxt][e] = s;
				}
				if (!visited[nxt]) {
					visited[nxt] = 1;
					que.push(nxt);
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	while (M--) {
		int x, y, c; cin >> x >> y >> c;
		x--, y--;
		G[x].emplace_back(MP(y, c));
		if (y == 0) {
			G[N].emplace_back(MP(x, c));
		}
	}

	bfs();

	int ans = 1000000007;
	int ansnode = -1;
	int MX = (1 << N) - 1;
	for (auto p : G[N]) {
		int node = p.first, c = p.second;
		if (dp[MX][node]) {
			int val = max(dp[MX][node], c);
			if (val < ans) {
				ans = val;
				ansnode = node;
			}
		}
	}

	if (ans == 1000000007) cout << -1;
	else {
		cout << ans << '\n';
		vector<int> stk;
		while (ansnode) {
			stk.emplace_back(ansnode);
			int tmp = old[MX][ansnode];
			MX ^= (1 << ansnode);
			ansnode = tmp;
		}
		cout << 1 << ' ';
		while (!stk.empty()) {
			cout << stk.back() + 1 << ' ';
			stk.pop_back();
		}
	}
}