[BOJ/Platinum 5] 백준 24519 Bottleneck Travelling Salesman Problem (Large)(C++)

문제 링크

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

 

 

문제

외판원 순회 문제는 영어로 Traveling Salesman Problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 이 중 변종 문제 중 하나인 Bottleneck Traveling Salesman Problem (BTSP) 문제를 살펴보자.

정점의 개수가 N개, 비용이 있는 간선이 M개인 방향 그래프가 주어진다. 어느 한 정점에서 출발해, 출발한 정점을 제외한 N − 1개의 정점을 모두 한 번씩 방문하고 다시 처음 정점으로 돌아오는 순회를 찾으려고 한다. 이러한 순회는 여러 가지가 있을 수 있는데, 정점 간 이동 비용의 최댓값을 최소화하려고 한다.

그래프가 주어졌을 때, 정점 간 이동 비용의 최댓값을 최소화하면서 모든 정점을 방문하는 순회를 찾아보자.

 

입력

첫 번째 줄에는 정점의 개수 N과 간선의 개수 M이 주어진다. (2 ≤ N ≤ 18, 0 ≤ M ≤ N(N − 1))

두 번째 줄부터 M개의 줄에 걸쳐서 간선에 대한 정보가 세 정수 u, v, c로 주어진다. 이는 정점 u에서 v로 향하는 비용이 c인 간선이 있음을 의미한다. 두 정점 사이에 같은 방향의 간선이 2개 이상 존재하지 않는다. (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ c ≤ 5,000,000)

 

출력

모든 정점을 방문하는 순회가 있다면 첫 번째 줄에 정점 간 이동 비용의 최댓값의 최솟값을 출력한다. 만약에 이러한 순회가 없는 경우 -1을 출력한다.

모든 정점을 방문하는 순회가 있다면, 다음 줄에 정점 간 이동 비용의 최댓값을 최소화하도록 방문해야 하는 정점 번호를 순서대로 N개를 출력한다. 이러한 순회가 여러 가지가 있는 경우 아무것이나 출력해도 된다.

 

예제 입력 1

3 6
1 2 4
2 3 4
3 1 4
1 3 2
3 2 3
2 1 5

예제 출력 1

4
1 2 3

예제 입력 2

2 1
1 2 3

예제 출력 2

-1

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

각 상태(지금까지 방문한 정점, 현재 방문하는 정점)마다 이동 비용을 누적하는 게 아니고 간선을 지날 때마다 발생하는 비용의 최댓값의 최솟값을 기록해야 한다.

1번째 정점에서 출발하여, 모든 정점을 방문하고 다시 1번째 정점으로 올 수 없으면 -1을 출력한다.

모든 정점을 방문하고 다시 1번째 정점으로 올 수 있으면, 순회 경로의 이동 비용의 최댓값이 될 수 있는 수 중 최솟값을 출력한다.

다음은 경로 역추적인데, 다시 1번째 정점에서 출발하여 N개의 정점을 방문하는데, 미리 기록해 둔 각 상태마다의 이동 비용의 최댓값을 비교하면서 이동해야 한다.

경로 역추적하는 게 너무 어려워서 검색해서 해결했다.

[BOJ 24519] 백준 24519번 - Bottleneck Travelling Salesman Problem (Large)

 

 

코드

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

using namespace std;
int N, M, U, V;
LL C;
LL Dist[MAX][MAX];
LL DP[1 << MAX][MAX];
int Path[MAX];
LL Answer = INF;

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 >> M;
	for (int i = 0; i < M; i++) {
		cin >> U >> V >> C;
		Dist[U - 1][V - 1] = C;
	}
}

LL getTsp(int Bitmask, int Now) {
	if (Bitmask == (1 << N) - 1) {
		return DP[Bitmask][Now] = ((Dist[Now][0] == 0) ? INF : Dist[Now][0]);
	}

	if (DP[Bitmask][Now] != -1) {
		return DP[Bitmask][Now];
	}

	LL MinDist = INF;

	for (int i = 0; i < N; i++) {
		if (Dist[Now][i] == 0) continue;
		if ((Bitmask & (1 << i)) == 0) {
			LL NextDist = getTsp(Bitmask | (1 << i), i);
			MinDist = min(MinDist, max(NextDist, Dist[Now][i]));
		}
	}
	
	return DP[Bitmask][Now] = MinDist;
}

void findPath(int Bitmask, int Now, int Depth) {
	Path[Depth] = Now + 1;

	if (Bitmask == (1 << N) - 1) {
		if (Dist[Now][0] > 0) {
			for (int i = 0; i < N; i++) {
				cout << Path[i] << " ";
			}
			cout << "\n";
			exit(0);
		}
		return;
	}

	for (int i = 0; i < N; i++) {
		if (Dist[Now][i] == 0) continue;
		if (((Bitmask & (1 << i)) == 0) && (DP[Bitmask][Now] == max(DP[Bitmask | (1 << i)][i], Dist[Now][i]))) {
			findPath(Bitmask | (1 << i), i, Depth + 1);
		}
	}
}

void settings() {
	Answer = getTsp(1, 0);
}

void printAnswer() {
	if (Answer == INF) {
		cout << "-1\n";
	}
	else {
		cout << Answer << "\n";
		findPath(1, 0, 0);
	}
}

int main() {
    FASTIO

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

    return 0;
}