BOJ 10971번 외판원 순회2

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

github : https://github.com/junho0956/Algorithm/blob/master/10971/10971/%EC%86%8C%EC%8A%A4.cpp

 

TSP, 외판원 순회는

한 정점에서 모든 정점을 중복없이 방문하고 다시 첫 정점으로 되돌아오는 최단거리를 의미합니다

 

일반적으로 TSP를 해결하기 위해서는 정점이 N 개일때 N! 이라는 시간이 필요하게 됩니다.

이 문제에서는 정점이 최대 10개이기 때문에 10! = 3628800번의 시간복잡도가 필요하게 됩니다.

시간제한도 2초이기 때문에 완전탐색으로 10! 으로 문제를 해결할수도 있습니다

하지만 정점이 커질수록 TLE 가 될수밖에 없기 때문에 제대로된 방법을 알아보겠습니다

(2098번 외판원 순회 https://www.acmicpc.net/problem/2098 의 경우 16! = 20조이상의 시간복잡도가 필요하게됩니다)

 

먼저 외판원을 순회할때의 시작정점은 어떤 정점이든 상관없습니다.

방향트리를 가정하고 있기 때문에 시작정점에 따라 값이 다를 수 있다 생각할 수 있는데,

결국 최단거리인 TSP를 찾게되면 그 정점들은 사이클이 생기기 때문입니다

(ex 1 -> 2 -> 3 == 2->3->1 == 3->1->2) 

 

알고리즘 수업시간 때 배운 TSP에 대해서 설명해보겠습니다.

TSP는 시간복잡도를 줄이기 위해서 동적계획법에 의한 계산을 하게 됩니다

 

기본적인 DP의 점화식은 다음과 같습니다

위에서 시작정점은 어디든 상관없다고 말씀드렸으니, 시작정점은 1이라고 가정하고

{V} 를 방문하지 않은 정점이라고 가정하겠습니다.

"dp[i][{V} 의 의미는 정점 i 에서 출발해서 아직 방문하지 않은 정점집합V 를 거쳐 정점 1로 되돌아오는 최단거리"

를 의미하게 됩니다.

 

결국 dp[v1][{V-v1}] = min (2<=j<=k) (cost[1][j]+DP[j][{V-v1,vj}] 라는 점화식을 만들 수 있게 됩니다.

 

하지만 이 DP는 단순하게 구현하려면 엄청나게 많은 메모리가 필요하게 됩니다.

정점 1 2 3 4 5 가 있을 때

정점 1에서 출발하여 만들어볼 수 있는 DP는

1 2 3 4 5

1 2 3 5 4

1 2 4 3 5

1 2 4 5 3

1 2 5 3 4

1 2 5 4 3

1 3 . . .

이렇게 DP는 어떤 정점에서 어떤 정점을 거쳤는지에 대한 순서와 값들을 알고 있어야되는 것입니다

 

이걸 단순히 배열로만 다 표현하려면 엄청나게 많은 메모리가 들 수 밖에 없습니다

그렇기때문에 이 순서들을 DP로 표현하기 위해서는 비트마스킹을 이용해야 합니다

그렇게되면 좀더 수월하게 이 집합의 순서와 값들을 유지하면서 DP를 계산할 수 있습니다

 

풀이과정은 다음과 같습니다.

배열은 최대정점이 N일때 1<<N 의 크기가 필요하다

현재 출발하려는 정점이 start 이고, 지금까지 방문한 정점들의 순서를 비트마스킹을 이용해서 visit으로 표현한다

비트마스킹 visit이 모든정점을 방문했다면 현재 도착한 마지막 정점에서 정점1로 가는 값을 반환합니다

모든 정점을 방문하지 않았다면 현재까지 정점에 대한 DP 값을 확인합니다

만약 DP 가 초기값이 아니라면, 이는 이미 이 순서에 대한 최단거리를 가지고 있는 것이므로 반환합니다

만약 DP 가 초기값이라면, 현재 정점부터 정점1을 제외한 방문할 수 있는 모든 정점을 확인합니다

 

비트마스킹으로 풀이하면, 현재 방문한 값과 순서는 visit에 담겨있습니다

정점 i 를 방문했는지 확인하는 방법

-> (visit & (1<<i)) == 0 이면 방문하지않음, ==1 이면 방문함

다음 방문할 정점에 대해 지금까지 방문한 값 visit을 갱신하는 방법

-> (visit | (1<<i)

 

#include <iostream>
#include <algorithm>
using namespace std;
 
#define INT_MAX 99999999
 
int arr[10][10];
int dp[10][1 << 10];
int N, visit_check;
 
int TSP(int start, int visit) {
    if (visit == visit_check) {
        if (arr[start][0] == 0) return INT_MAX;
        else return arr[start][0];
    }
 
    int& result = dp[start][visit];
    if (result) return result;
 
    int len = INT_MAX;
    for (int i = 1; i < N; i++) {
        if (arr[start][i] != 0 && (visit&(1 << i)) == 0)
            len = min(len, arr[start][i] + TSP(i, visit | (1 << i)));
    }
 
    return result = len;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> arr[i][j];
 
    visit_check = (1 << N) - 1;
 
    cout << TSP(0, 1);
    return 0;
}