[10971번] 외판원 순회2 (TSP)

외판원 순회, Traveling Salesman Problem 이라고 불리는 이 문제는 가장 활용도가 높고 중요하게 여겨지는 문제입니다.

[문제] 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다.(길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 

이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

[예제입력] 

4

0 10 15 20

5 0 9 10

6 13 0 12

8 8 9 0

[예제출력]

35

출발하는 도시(i)와 도착하는 도시(j)를 모두 표시하는 W[i][j]의 행렬로 나타내기 때문에 입력은 NxN의 형태로 주어집니다.

도시는 건너뛸 수 없기 때문에 출발하는 도시를 표시하는 행렬의 원소 중 열(row) 번호는 다음 도시의 행(column) 번호와 일치해야 합니다..

(ex. W[1][2] - W[2][3] - W[3][4] - W[4][1] 식의 순서로 완성돼야 한다. W[1][2]-W[3][4]-... 식으로 이어질 수 없음)

즉, 원소의 행(column)만 정해주면 열(row)은 자동으로 정해지기 때문에 행(column) 순서의 경우의 수(순열)만 구하면 됩니다.

(1)  열(row) 1,2,3,4의 모든 순열과 해당하는 행렬을 표시해보자

1-2-3-4 = W[1][2]-W[2][3]-W[3][4]-W[4][1]

(벡터(배열) 번호로 표현하면, i - i+1 - i+2 - i+3 = W[i][i+1] - W[i+1][i+2] - W[i+2][i+3] - W[i+3][i+4])

1-2-4-3 = W[1][2]-W[2][4]-W[4][3]-W[3][1]

1-3-2-4 = W[1][3]-W[3][2]-W[2][4]-W[4][1]

1-3-4-2 = W[1][3]-W[3][4]-W[4][2]-W[2][2]

.

.

.

총 N! 의 개수가 나옵니다.

조건 : 원소가 0이면 가는 길이 없다는 뜻이므로 원소가 0이 아닐 때만 Count합니다.

next_permutation 으로 모든 순열을 돌아가면서 계산하고 최소값을 구하면 정답을 구할 수 있습니다.

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;    // 행렬의 크기(도시의 개수)를 입력받는다
    
    int w[n][n];
    
    for(int x = 0; x < n; x++)    // 행렬의 원소(도시간의 이동거리)를 입력받는다
    {
        for(int y = 0; y < n; y++)
        {
            cin >> w[x][y];
        }
    }
    
    int result = 10000001;    // 최소값을 구해야 하므로 가능한 최대거리를 초기값으로 설정한다. (도시의 개수 10개 이하, 도시 거리 최대 1,000,000 = 최대 거리 수 10 x 1,000,000)
    int pres = 0;    // 최소값을 구하기 위한 임시 저장변수
    
    vector<int> v(n);
    
    for(int i = 0; i < n; i++)    // 행(column) 번호 값을 벡터에 대입
    {
        v[i]=i;
    }
    
    do
    {
        for(int i=0;i<n;i++)    
        {
            int j = i+1;    // 원소의 행(column)은 다음 원소의 열(row)이 된다. (1) 설명 참조
            if(i+1 >= n)    // 도시의 개수보다 많아질 때, 마지막 원소의 열(row)은 처음 도시로 돌아간다. (1) 설명 참조
            {
                j = 0;
            }
            if (w[v[i]][v[j]] == 0)        // 가는길이 없으면 계산하지 않고 pres에 최대값을 대입 (거리계산이 되지 않도록 함)
            {
                pres = 10000001;
            }
            
            pres = pres + w[v[i]][v[j]];    // 각각 원소값을 더해서 총 거리 값을 계산
        }
        if(pres < result)    // 초기값(10000001)보다 작으면 result에 
        {
            result = pres;
        }
        pres = 0;
        
    }
    while(next_permutation(v.begin(),v.end()));
    
    cout << result << endl;
}