TSP 구현 - 2 (Memoization 추가)

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include <iostream> #include <stdio.h>   using namespace std;   #define    INF 987654321 #define MAX_N 6 int N, Graph[MAX_N][MAX_N]; // memoization을 적용하기 위한 array 변수 입니다.  int Memo[MAX_N][1<<MAX_N];   int solve(int pos, int visited) {     // memoization을 적용하여 검색 횟수를 줄입니다.     if (Memo[pos][visited] != -1) return Memo[pos][visited];       if (visited == (1 << N) - 1)         return 0;       int ret = INF;     for (int next = 0; next < N; ++next)     {         // 1. 방문 여부를 확인하고         // 2. 간선 유무를 확인합니다. (단, full mesh-모든 간선 존재- 의 경우에는 항상 참입니다)          if (!(visited & (1 << next)) && Graph[pos][next])         {             int tmp = Graph[pos][next] + solve(next, visited | (1 << next));             if (tmp < ret)                 ret = tmp;         }     }       Memo[pos][visited] = ret;     return ret; }   int main() {     int tcCnt;     freopen("tsp_input.txt", "r", stdin);     cin >> tcCnt;     for (int t = 1; t <= tcCnt; ++t)     {         cin >> N;           for (int i = 0; i < N; ++i)         {             for (int j = 0; j < 1 << N; ++j)             {                 Memo[i][j] = -1;             }         }           for (int i = 0; i < N; ++i)             for (int j = 0; j < N; ++j)                 cin >> Graph[i][j];           int ans = INF;         for (int i = 0; i < N; ++i)         {             int tmp = solve(i, 1 << i);             if (ans > tmp) ans = tmp;         }         cout << "#" << t << ' ' << ans << endl;     }     return 0; } Colored by Color Scripter

cs