백준[2098] 외판원 순회

문제 설명

문제 링크

http://icpc.me/2098

2098번: 외판원 순회

풀이

TSP(Traveling saleperson)라고 불리는 웰노운 문제다.

비트마스크와 dp를 이용하여 문제를 풀 수 있다. 

dp 정의는 dp[n][state] = 1부터 시작하여 state에 있는 점을 모두 지나 n번 노드까지 올 때 필요한 최소 비용으로 할 수 있다.

어느 정점에서 시작하던 사이클을 돌기 때문에 시작 정점은 고려할 필요가 없다.

나는 마지막 노드에서 0번 노드로 다시 돌아갈 경우에 dp[cur][0]이 0일 수 있는 경우를 빠트려 시간을 많이 잡아먹었다.

코드

top down

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int d[17][17], dp[17][1 << 16], N;

int dpf(int cur, int state) {
    int &ret = dp[cur][state];
    if (~ret) return ret; // ret != -1일 경우
    //모든 노드를 방문했을 경우
    if (state == ((1 << N) - 1)) {
    	//마지막 노드에서 다시 0번 노드로 이동
        if (d[cur][0] != 0) return d[cur][0];
        else return 1e9;
    }
    int ans = 1e9;
    for (int i = 0; i < N; i++) {
        if (state & (1 << i) || d[cur][i] == 0) continue; 
        ans = min(ans, dpf(i, state | (1 << i)) + d[cur][i]);
    }
    return ret = ans;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < N; j++)
            scanf("%d", &d[i][j]);
    memset(dp, -1, sizeof(dp));
    // 0번 노드에서 시작하여 상태는 0번 노드만 방문한 상태
    int ans = dpf(0, 1);
    printf("%d\n", ans);
}

bottom up

탑다운 dp정의와 약간 다르게 state에 있는 점들에 시작할 때 지나는 0을 포함하지 않는다.

#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 1e8;
int dp[1 << 16][20];
int w[20][20];

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);

	// 초기화
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) dp[i][j] = INF;
    }
    for (int i = 0; i < n; i++) {
        if (w[0][i]) dp[1 << i][i] = w[0][i];
    }

    for (int state = 1; state < (1 << n); state++) {
        for (int i = 0; i < n; i++) {
            if (!(state & (1 << i))) continue;
            for (int j = 0; j < n; j++) {
            // state에 있는 점을 모두 지나 i -> j로 가는 상태
                if (!(state & (1 << j))) continue;
                if (w[i][j]) dp[state][j] = min(dp[state][j], dp[state & ~(1 << j)][i] + w[i][j]);
            }
        }
    }
    // 0부터 시작하여 모든 점을 지나 다시 0에 도착한 최솟값
    printf("%d", dp[(1 << n) - 1][0]);
}

top down ver.2 모든 점을 다 방문했을 때부터 시작하는 경우 + 역추적

#include <cstdio>
#include <cstring>

const int inf = 1e9;
int dp[17][1 << 17], n;
int w[17][17];
int p[17][17];

int dpf(int cur, int state) {
    int &ret = dp[cur][state];
   if (~ret) return ret;
   if (!state) {
      if (!cur) return 0;
      else return inf;
   }
   ret = inf;
   for (int i = 0; i < n; i++) {
      if (!(state & (1 << i)) || !w[i][cur]) continue;
      int tmp = dpf(i, state & ~(1 << i)) + w[i][cur];
      if (ret > tmp) {
         ret = tmp;
         p[cur][state] = i;
      }
   }
   return ret;
}

void trace(int cur, int state) {
   if (p[cur][state] == -1) return;
   int nxt = p[cur][state];
   trace(nxt, state & ~(1 << nxt));
   printf("%d ", cur + 1);
}

int main() {
   memset(dp, -1, sizeof dp);
   memset(p, -1, sizeof p);
   scanf("%d", &n);
   for (int i = 0; i < n; i++) 
      for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
   printf("%d\n", dpf(0, (1 << n) - 1));
   printf("1 "); // 시작점
   trace(0, (1 << n) - 1); // 지나가는 경로
}

cf) 외판원 순회 경로 추적

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 1e8;
int dp[1 << 16][20];
int par[1 << 16][20];
int w[20][20];
int path[20];

int main() {
    int n; scanf("%d", &n);
    memset(par, -1, sizeof par);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);

    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) dp[i][j] = INF;
    }
    for (int i = 0; i < n; i++) {
        if (w[0][i]) dp[1 << i][i] = w[0][i];
    }

    for (int state = 0; state < (1 << n); state++) {
        for (int i = 0; i < n; i++) {
            if (!(state & (1 << i))) continue;
            for (int j = 0; j < n; j++) {
                if (!(state & (1 << j))) continue;
                if (w[i][j] && dp[state][j] > dp[state & ~(1 << j)][i] + w[i][j]) {
                    dp[state][j] = dp[state & ~(1 << j)][i] + w[i][j];
                    par[state][j] = i;
                }
            }
        }
    }

    printf("최소 비용: %d\n", dp[(1 << n) - 1][0]);
    int cur = 0, state = (1 << n) - 1, idx = n;
    path[0] = 0;
    while (~cur) {
        path[idx--] = cur;
        int tmp = state;
        state &= ~(1 << cur);
        cur = par[tmp][cur];
    }

    printf("최적 경로: ");
    for (int i = 0; i <= n; i++) printf("%d ", path[i] + 1);
}