[백준] 알고리즘 10971번 - 외판원 순회 2문제

문제

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

10971번: 외판원 순회 2

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int arr[11][11];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        v[i] = i;
    }
    int ans = 210000000;
    do {
        bool flag=true;
        int sum = 0;
        for (int i = 0; i < n-1; i++) {
            if (arr[v[i]][v[i + 1]] == 0) {
                flag = false; 
            }
            else {
                sum += arr[v[i]][v[i + 1]];
            }
        }
        if (flag&& arr[v[n - 1]][v[0]]!=0) {
            sum += arr[v[n - 1]][v[0]];
            ans = min(sum, ans);
        }
    } while (next_permutation(v.begin(), v.end()));
    cout << ans;
}

해설

TSP문제

단, 한 번 갔던 도시로는 다시 갈 수 없다. 
비용은 대칭적이지 않다.

즉 모든 경우의 수를 해보는데 순열을 이용하여 해결할 수 있다.

벡터 v는 n까지의 순열의 순서를 저장하게 해준다.

순열의 순서v에 따라서 만들 수 있는 도시간의 거리의 최솟값을 구해주면된다.

마지막으로 마지막 도시까지 간다음 다시 처음도시로 돌아와야하는데, 이 경우의 처리도 해줘야한다.

 

경우의 수를 조금 줄일 수 있다.

문제에서 다시 처음 도시로 돌아갸아 한다는 지문때문에 처음 시작순열을 고정시켜도 상관없다.

1 2 3 4

2 3 4 1

3 4 1 2

4 1 2 3

 

모두 같은 경우의 수라고 봐도 무방하다. 결국엔 1 2 3 4 1 을 하는건데 , 아래와 같은 4가지 전부다 이와같다.

즉 next_permutation(v.begin()+1, v.end())

시작점을 고정해둔 상태로 그 다음 위치부터 순열을 구하기 때문에 O(N*N-1!)의 시간복잡도가된다.