외판원 순회 (Traveling Salesman Problem)

외판원 순회 문제 

- 여러 도시가 있고 도시 간 이동 비용이 있을 때 모든 도시를 한 번씩만 방문하여 시작 위치로 돌아오는 경로의 최소 비용을 구하는 문제.

 

각 도시가 20개라하면 20개의 도시를 모두 방문하는 경우의 수는 20! 이 된다.

모두 계산하지 않고  bitmask + memoization을 이용한다.

 

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

2098번: 외판원 순회

 

왜 dp[1<<16] 가 아닌 dp[1<<16][16] 이 필요할까?

 

dp[1<<N] 만 사용한다고 해보자.

1,2,3번 3개의 도시가 있고 1->3 과 3->1 의 경로와 3->2 경로는 있지만 1->2 의 경로는 없다고 해보자.

 

먼저 1->3->2 의 경로를 탐색하고 dp[101]의 값을 갱신한다.

이후에 3->1 의 순서로 왔을 때 3->1->2 의 경로는 없지만 dp[101]의 값을 리턴하게 된다.

 

그래서 dp[101][3] 과 dp[101][1] 을 다르게 취급해줘야 한다.

( 현재 위치와 남은 도시의 집합이 같아야 계산을 안 해도 된다고 생각 ) 

 

풀이 

#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 987654321
using namespace std;
int n;
int cost[16][16];
int dp[1 << 16][16];
 
int dfs(int state, int here) {
    if (state == (1<<n)-1) {
        if (cost[here][0] != 0) {
            return cost[here][0];
        }
        else return INF;
    }
    int &ret = dp[state][here];
    if (ret != -1) return ret;
 
    ret = INF;
 
 
    for (int i = 0;i < n;i++) {
        if (cost[here][i] == 0) continue;
        if ((state&(1 << i)) == 0) {
            ret = min(ret, dfs(state | (1 << i), i) + cost[here][i]);
        }
    }
    
    return ret;
 
}
 
 
int main() {
    scanf("%d", &n);
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            scanf("%d", &cost[i][j]);
        }
    }
 
    memset(dp, -1, sizeof(dp));
    
    int ans=dfs(1, 0);
 
    printf("%d", ans);
 
    return 0;
}