백준 10971 - 외판원 순회 2

문제

 

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

10971번: 외판원 순회 2

 

 

풀이

 

모든 도시를 방문하고, 도시의 방문 순서를 다르게 하는 문제이다. 도시의 수는 최대 10개이다. 그러므로 가능한 방문 순서의 수는 10! 이 되고, 이를 순열을 이용해 나타낸다.

 

d 배열을 이용해 도시를 저장하고, next_permutation() 함수를 이용해 d 배열의 가능한 순열을 만든다.

W[i][j]가 i 에서 j 로 가는 비용을 나타내므로, W[ d[i] ][ d[i+1] ] 을 이용하면 각각의 d 배열의 순열에서 도시 방문의 비용을 알 수 있다.

 

W[ d[i] ][ d[i+1] ] = 0 일 경우 d[i] 에서 d[i+1]로 갈 수 없는 경우이므로, 이 때는 비용을 구할 수 없다.

 

 

코드

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int W[10][10];
int d[10];
int result = 987654321;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> 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;
 
    do
    {
        int sum = 0;
        bool ok = true;
        for (int i=0; i<N-1; i++)
        {
            if (W[d[i]][d[i+1]])
                sum += W[d[i]][d[i+1]];
            else
                ok = false;
        }
 
        if (W[d[N-1]][d[0]])
            sum += W[d[N-1]][d[0]];
        else
            ok = false;
 
        if (ok && result > sum)
            result = sum;
    } while (next_permutation(d+1, d+N));
 
    cout << result;
 
    return 0;
}