[BOJ] 24512 - Bottleneck Traveling Salesman Problem (Small)

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

BOJ - Bottleneck Traveling Salesman Problem (Small)

문제 유형: TSP(Traveling Salesman Problem), 브루트포스, 백트래킹

문제 난이도: Silver II

시간 제한: 1초

메모리 제한: 1024

 

문제

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

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

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

 

입력

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

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

 

출력

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

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

 

풀이

모든 경우의 수를 구하면 된다.

어차피 한 바퀴를 돌아야하므로, 시작점을 1로 고정해도 상관없다.

방문한 적이 없으면, 방문처리하고 깊이방문한뒤 돌아와서 방문을 취소해주는 식으로 하면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int ans = INT_MAX;
vector<int> ans_trace;
int n, m;

bool visitedall(vector<bool> &visited) {
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) return false;
    }
    return true;
}

void dfs(int node, int cost, vector<vector<pii>> &adj, vector<bool> &visited,
         vector<int> &trace) {
    if (node == 1 && visitedall(visited)) {
        if (cost < ans) {
            ans_trace = trace;
            ans = cost;
        }
        return;
    }
    for (const auto &[e, w] : adj[node]) {
        if (!visited[e]) {
            visited[e] = true;
            trace.emplace_back(e);
            dfs(e, max(cost, w), adj, visited, trace);
            trace.pop_back();
            visited[e] = false;
        }
    }
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    vector<vector<pii>> adj(n + 1);
    vector<bool> visited(n + 1, false);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
    }

    vector<int> trace = {1};
    dfs(1, -1, adj, visited, trace);

    if (ans == INT_MAX) {
        cout << "-1\n";
        return 0;
    }
    cout << ans << "\n";
    for (int i = 0; i < ans_trace.size() - 1; i++) {
        cout << ans_trace[i] << " ";
    }
    cout << "\n";

    return 0;
}