[10971번] 외판원 순회 2

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

10971번: 외판원 순회 2

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 유명한 문제 중 하나입니다.

모든 도시를 거쳐가는 순서들 중 가장 적은 비용을 들이는 외판원의 순회 경로를 구하는 것인데요.

한번 갔던 도시로는 다시 갈 수 없고, 모든 도시를 거친 후 다시 원래의 도시로 돌아와야 합니다.

세부 문제 내용은 위 링크를 참조하시면 됩니다.

 

결국 1~N번까지의 도시를 일렬로 줄을 세워서 갈 수 있는 도시들을 확인 하고 도시간에 이동하는데 드는 최소 비용을 구하는 것입니다.

순열을 이용하여 도시를 줄을 세운 후 각각의 경로의 비용을 합산해주어 최소값을 구하면 되겠습니다.

브루트포스 알고리즘을 이용할 때는 전체 경우의 수를 계산해주어야 합니다.

도시의 수 N의 범위는 2 ≤ N ≤ 10 이므로 최대 10일 때를 기준으로 계산해보면 10개의 도시를 일렬로 줄 세우는 경우의 수는 \(10!\)이 됩니다.

\(10! = 3,628,800\)이므로 360만가지라는 숫자는 1억가지의 경우의 수가 1초가 걸린다고 했을 때 큰 숫자가 아닙니다.

또한 비용을 계산할 때 \(O(n)\)이 걸리게 되므로 \(O(n*n!)\), 최대 \(11! = 39,916,800\)의 시간 복잡도를 가지게 됩니다.

고로 브루트포스 알고리즘 순열을 이용할 수 있습니다.

 

ans 변수의 초기화에 주의합니다.

최소 비용을 구해야하므로 0으로 초기화시 최소값을 구할 수 없게 됩니다.

 

 

[코드1]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
    int n;
    cin >> n;
    vector<int> a(n); //도시번호저장
    for (int i = 0; i < n; i++) {
        a[i] = i; //0부터 n-1까지 번호로 매김
    }
    int cost[n][n]; //cost[i][j] = i번 도시에서 j번 도시로 가기 위한 비용
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }
    //최소값 초기화 주의
    int ans = 2147483627;
    do {
        bool isOk = true; //해당 순열에서 전체 도시들을 방문할 수 있을 때만 true
        int sum = 0;
        for (int i = 0; i < n - 1; i++) {
            if (cost[a[i]][a[i + 1]] == 0) {
                isOk = false; //방문할 수 없을 경우 false로 기록
                break;
            } else {
                sum += cost[a[i]][a[i + 1]];
            }
        }
        //마지막 도시에서 원래 도시로 돌아올 수 있는지 체크
        if (isOk && cost[a[n - 1]][a[0]] != 0) { //방문할 수 있으면서 마지막 도시에서 원래 도시로 돌아올 수 있다면
            sum += cost[a[n - 1]][a[0]]; //마지막도시에서 처음도시로 가는 비용을 더함
            if (ans > sum) ans = sum;
        }
    } while(next_permutation(a.begin(), a.end()));
    cout << ans << '\n';
    return 0;
}

[결과]

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
35 //output

 

 

 

여기서 나아가 시간 복잡도를 \(O(n!)\)으로 개선할 수가 있습니다.

그 이유는 마지막 도시에서 원래 도시로 돌아올 수 있다는 문제의 조건 때문입니다.

결국 원형의 모양으로 도시를 순회하게 되는 것인데요.

첫번째 도시를 고정시킨 후 두번째부터 마지막 순열까지의 순열만 구해서 계산을 해보면 됩니다.

 

예시로 아래의 순열을 비교해보면 끝이 이어져 있기 때문에 결국 동일한 순열입니다.

1 2 3 4
2 3 4 1 
3 4 1 2 
4 1 2 3

1, 2, 3, 4로 생각을 해보면,

1로 시작하는 순열은 6가지가 있습니다. 2, 3, 4도 마찬가지로 6개씩 있어요. 

1로 시작하는 순열들과 2로 시작하는 순열들을 실제로 서로 매치해보면서 따져보면 동일한 순열로 표현됩니다. 3, 4로 시작하는 순열들도 결국 동일해요.

즉, 1로 시작하는 순열만 따져보면 되는 것이므로 전체 순열 가지수는 \(4!\) 인데 1로 고정시킨 것만 계산을 하면 되니까 \(3!\)으로 경우의 수가 확 줄게 되지요.

코드1에서 딱 한 줄만 바꿔주면 시간 복잡도를 \(O(n!)\)으로 줄일 수 있습니다.

 

 

[코드2]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main () {
    int n;
    cin >> n;
    vector<int> a(n); 
    for (int i = 0; i < n; i++) {
        a[i] = i;
    }
    int cost[n][n]; 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }
    int ans = 2147483627;
    do {
        bool isOk = true; 
        int sum = 0;
        for (int i = 0; i < n - 1; i++) {
            if (cost[a[i]][a[i + 1]] == 0) {
                isOk = false; 
                break;
            } else {
                sum += cost[a[i]][a[i + 1]];
            }
        }
        if (isOk && cost[a[n - 1]][a[0]] != 0) { 
            sum += cost[a[n - 1]][a[0]]; 
            if (ans > sum) ans = sum;
        }
    } while(next_permutation(a.begin() + 1, a.end()));//맨 시작부분을 고정해두고 두번째부터 순열을 구함
    cout << ans << '\n';
    return 0;
}

 

[결과]

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
35 //output