2098 - 외판원 순회

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

문제 <외판원 순회 2>의 실행시간이 오래 걸리는 이유는 모든 정점을 방문했는 지 확인하는 반복문과 이미 방문한 경로의 불필요한 탐색때문이다.

비트마스킹을 통해 이러한 반복을 줄여보자. 정점의 개수는 최대 16이다. 0번째, 1번째, ... 15번째를 방문했는지를 비트마스킹을 통해 00.....0 과 같이 길이가 16인 2진수로 표현할 수 있다. 그럼 $O(1)$만에 종료 조건을 확인할 수 있다.

하지만 모든 경우를 탐색하는 것은 똑같아서 수행시간에 큰 차이는 없을 것이다. (N배 빠르니까 약 10배)

여러 정점을 방문하면서 남은 정점을 확인할 때 중복되는 경우가 많다. 예를 들면 1 2 5 3 4 순으로 방문한 경우와 2 1 5 3 4 순으로 방문한 경우는 둘 다 1, 2를 방문한 상태에서 5 3 4 를 다시 방문하고 있다. 5 3 4 순으로 방문했을 때의 최적값을 구해둔다면 다시 방문할 필요 없이 미리 구한 최적해를 사용하면 된다. (메모이제이션으로 구현함)

이전에 작성한 글에서 소스의 다른 부분은 모든 정점을 방문했는 지 확인하는 반복문을 없애고 O(1)의 비트로 확인한다는 점과, 메모이제이션을 적용했다는 점 밖에 다르지 않다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

int dp[17][1<<17];
int g[17][17], n;

int tsp(const int& first, int cur, int state, bool start=false){
    if(!start && cur==first){
        if( state == (1<<(n+1))-1 ) return 0;
        return INF;
    }
    
    int& r = dp[cur][state];
    if(r != -1) return r;
    
    r = INF;
    for(int i=1; i<=n; ++i){
        if(g[cur][i] > 0 && (state & (1<<i)) == 0){
            r = min(r, g[cur][i] + tsp(first, i, state | (1<<i)));
        }
    }
    return r;
}

int main(){
    int i, j;
    scanf("%d", &n);
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            scanf("%d ", &g[i][j]);
            
    memset(dp, -1, sizeof(dp));
    printf("%d", tsp(1, 1, 1, true));
    return 0;
}