10971번

10971번 - 외판원 순회2

유명한 TSP(traveling salesman problem) 인 외판원 순회다.

이 문제는 N 제한이 작기 때문에 (N<=10) 이므로 완전 탐색을 통해서 풀 수있다.

1. 재귀로 순열을 구해서 푸는 방법

permutation 함수로 모든 순열을 구한뒤, 그 순열이 모든 정점을 방문할 수 있고 순회할 수 있는지 체크한다.

그러면서 모든 값들을 더해서 정답을 구한다.

2. next_permutation 으로 푸는 방법

##다른 사람 코드 보면서 배운 점

내가 짠 코드는 시간복잡고가 N! * N 이다.

하지만 어차피 순회이기 때문에, 시작점을 고정시키면 N!로 시간 복잡도를 줄일 수 있다!!

이는 next_permutation 에서 시작점을 next_permutation(order.begin()+1,order.end()) 로 바꿔서 할 수 있다.

재귀로 순열을 구할 때도 비슷한 방식으로 할 수 있다.

<정답 코드 - 재귀 순열>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int N;
vector<vector<int>> v;
int ans = 987654321;
bool visited[10];
 
void permutation(int len,vector<int> &order)
{
    if (len == N)
    {
        int sum = 0;
 
        for (int i = 0; i < order.size(); i++)
        {
            int now = order[i];
            int next;
 
            if (i+1 == order.size())
            {
                next = order[0];
            }
            else
            {
                next = order[i + 1];
            }
 
            if (v[now][next] == 0)
            {
                return;
            }
            else
            {
                sum += v[now][next];
            }
        }
 
        ans = min(ans, sum);
    }
 
    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            order.push_back(i);
 
            permutation(len+1,order);
 
            visited[i] = false;
            order.pop_back();
        }
    }
 
}
int main()
{
    cin >> N;
 
    v.resize(N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int tmp;
            cin >> tmp;
            v[i].push_back(tmp);
        }
    }
 
    vector<int> order;
    permutation(0,order);
 
    cout << ans << endl;
    return 0;
}

<정답 코드 - next_permutation 함수 사용 >

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int N;
vector<vector<int>> v;
int ans = 987654321;
 
int cal(vector<int> &order)
{
    int sum = 0;
 
    for (int i = 0; i < order.size(); i++)
    {
        int now = order[i];
        int next;
 
        if (i + 1 == order.size())
        {
            next = order[0];
        }
        else
        {
            next = order[i + 1];
        }
 
        if (v[now][next] == 0)
        {
            return 987654321;
        }
        else
        {
            sum += v[now][next];
        }
    }
 
    return sum;
}
int main()
{
    cin >> N;
 
    v.resize(N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int tmp;
            cin >> tmp;
            v[i].push_back(tmp);
        }
    }
 
    vector<int> order;
    for (int i = 0; i < N; i++)
    {
        order.push_back(i);
    }
 
    sort(order.begin(), order.end());
 
    do
    {
        ans = min(ans, cal(order));
 
    } while (next_permutation(order.begin(), order.end()));
 
    cout << ans << endl;
    return 0;
}