[BOJ] 10971. 외판원 순회2

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

10971번: 외판원 순회 2

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP)라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나라고 문제 설명에 나와있다.

실제로 학교 알고리즘 수업에서도 배운 기억이 있다.

 

이 문제에서는 n의 범위가 (2 ≤ N ≤ 10) 이므로 다음 순열을 이용해서 모든 경로를 구해볼 수 있다.

모든 경로에서의 비용을 계산해서 최솟값을 구해준다.

다음 순열은 d 벡터를 만들어서 사용한다.

d벡터에는 n만큼의 수가 들어있다. 예를 들어, n 이 4이면 d에는 0, 1, 2, 3의 값이 들어 있고 각각은 도시를 의미한다.

이 d 벡터의 모든 순열을 구해줘서 모든 경로를 구할 수 있다.

즉, d 벡터의 값이 도시의 번호와 마찬가지이므로 d벡터의 값을 w배열의 index로 사용하면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int w[10][10];
    vector<int> d(n);
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> w[i][j];
        }
    }
 
    for(int i=0; i<n; i++) {
        d[i] = i;
    }
 
    int ans = -1;
 
 
    //모든 경로 탐색
    do {
        int sum = 0;
        bool ok = true;
 
 
        //첫 번째 도시부터 마지막 도시까지의 비용을 더해준다.
        for(int i=0; i<n-1; i++) {
 
            //비용이 0인 경우, 즉 경로가 존재하지 않는 경우에는 ok를 false로 바꿔주고 break
            if(w[d[i]][d[i+1]] == 0) {
                ok = false;
                break;
            }
 
            sum += w[d[i]][d[i+1]];
        }
 
 
        //위에서 모든 경로가 존재하고(ok == true), 다시 마지막 도시에서 첫 번재 도시로 경로가 존재하는 경우
        //sum에 마지막 도시에서 첫 번째 도시로 가는 비용을 더해주고 최소값과 비교해준다.
        if(ok && w[d[n-1]][d[0]] != 0) {
            sum += w[d[n-1]][d[0]];
            if(ans == -1 || ans > sum) {
                ans = sum;
            }
        }
 
    } while(next_permutation(d.begin(),d.end()));
 
    cout << ans;
 
    return 0;
}