백준 10971: 외판원 순회2

순열을 이용해서 순회를 구하는 문제 조건에서 마을은 10미만이니 팩토리얼의 경우의 수를 이용해서 풀어 볼 수 있다. 시간 복잡도는 크게나오지만 단순하다. 마을 사이의 이동이 불가능한 경우는 불리언 변수로 제외시켜준다. 끝마을에서 처음마을로 갈 때는 똑같은 for문에 넣어주면 초과되니 따로 빼준다.

 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> dis(12);
vector<int> town;
int main()
{
    int input;
    cin >> input;
    for (int i = 0; i < input; ++i)
    for (int j = 0; j < input; ++j)
    {
        int temp;
        cin >> temp;
        dis[i].push_back(temp);
    }
    for (int i = 0; i < input; ++i)
        town.push_back(i);
    //순열에 따라 갈 수 있는지 여부를 판단한 후 거리를 구한다.
    int ans = 2147483647;
    do
    {
        int sum = 0;
        bool ok = true;
        for (int i = 0; i < input - 1; ++i)
        {
            if (dis[town[i]][town[i + 1]] == 0)
                ok = false;
            else
                sum += dis[town[i]][town[i + 1]];
        }
        
        if (ok && dis[town[input - 1]][town[0]] != 0)
        {
            sum += dis[town[input - 1]][town[0]];
            ans = min(ans, sum);
        }
    } while (next_permutation(town.begin(), town.end()));
    cout << ans << endl;
    return 0;
}