[10971번] 외판원 순회 2

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

외판원 순회 문제이다.

완전탐색으로도 해결 할 수 있으나 n이 커지면 O(N!)이므로 지양한다.

방문에 대한 처리를 bitmask로 처리하고 

모두 방문했을때 다시 시작점으로 갈 수 있다면 값을 계산해준다.

그리고 방문순서는 상관없고 모두 방문해야하는 것만 중요하니 비트마스크로 해결이 가능하다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <iostream> #include <memory.h>   #define MIN(a, b)(a < b ? a : b) #define INF 987654321   typedef long long ll;   int cost[20][20]; ll dp[20][1 << 16]; int n;   ll TSP(int here, int visit) {     ll &ret = dp[here][visit];     if (ret != -1)         return ret;       if (visit == (1 << n) - 1) {         if (cost[here][0] == 0)             return ret = INF;         return ret = cost[here][0];     }       ret = INF;     for (int i = 0; i < n; i++) {         if (visit & (1 << i) || !cost[here][i])             continue;           ret = MIN(ret, TSP(i, visit | (1 << 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));       printf("%lld", TSP(0, 1 << 0));          return 0; } Colored by Color Scripter

cs