백준 24512 (C++) Bottleneck Travelling Salesman Problem (Small)

최초 업로드: 2025-09-14 10:53:11

최근 수정 시간: 2025-09-14 10:53:11

게시자: rlatjwls3333

카테고리: 백준

# [Silver II] Bottleneck Travelling Salesman Problem (Small)

[문제 링크](https://www.acmicpc.net/problem/24512)

## 문제 설명

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

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

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

## 입력

첫 번째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($2 \le N \le 9$, $0 \le M \le N(N-1)$)

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

## 출력

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

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

## 풀이
백트래킹으로 TSP 경로를 찾아주었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 9;
const int INF = 0x3f3f3f3f;

int n, m, minCost=INF;
int cost[MAX][MAX];
bool visited[MAX];

vector<int> minVis, vis;

void dfs(int depth=1, int cur=0, int curCost=0) {
    if(depth==n) {
        if(cost[cur][0]) {
            int nextCost = max(curCost, cost[cur][0]);
            if(minCost>nextCost) {
                minCost=nextCost;
                minVis = vis;
            }
        }
        return;
    }

for(int i=0;i<n;i++) {
 if(cost[cur][i] && !visited[i]) {
 visited[i]=true;
 vis.push_back(i);
 dfs(depth+1, i, max(curCost, cost[cur][i]));
 vis.pop_back();
 visited[i]=false;
 }
 }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    while(m--) {
        int a, b, c; cin >> a >> b >> c;
        cost[a-1][b-1]=c;
    }
    visited[0]=true;
    vis.push_back(0);
    dfs();

if(minCost==INF) {
 cout << -1;
 } else {
 cout << minCost << '\n';
 for(int e : minVis) cout << e+1 << ' ';
 }
}
```