[c++] 백준 2098 - 외판원 순회(동적 계획법, 비트마스크)

0. [c++] 백준

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

1. 풀이

이 문제는 brute force의 형태로도 문제를 해결할 수 있지만, 그럴 경우 O(N!)으로 N이 15를 넘으면 대략 1조의 연산이 필요해지는데, 이렇게 될 경우 시간초과를 하는것은 당연한 소리이다.

따라서 이를 해결하기 위해서 동적계획법을 통해 한번 연산한 결과를 다시 재활용 하는 방식을 택하였다.

비트마스크 방식으로 방문한 위치를 확인하도록 하였다.

허나, 문제를 풀면서 하나 의문스러운 점이 있었는데, 바로 출발지점에 대한 의문이다.

처음 문제를 풀면서 출발 지점이 0이 아닌 모든 지점에서 가능한 것으로 생각하고 문제를 풀었지만, 이번 문제에서는 시작지점이 0으로 고정이었다.

뭐, 지문상에 나와있진 않지만, 이 때문에 괜히 30분정도를 날려먹은게 아깝네....

시작지점을 0으로 하고 문제를 해결하도록 하자.

2. 소스코드

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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115

////시간초과에 걸리는 brute force형식 //#include<iostream> //#include<vector> //#include<algorithm> // //using namespace std; // //int dist[16][16]; //bool visited[16]; //int N; //int INF = 1000000007; // //int dp(vector<int>& path, int adj = 0) { //    if (path.size() == N) //        return adj + dist[path.back()][path[0]]; // //    int ret = INF; //    for (int i = 0; i < N; i++) { //        if (visited[i]) //            continue; //        int here = path.back(); //        if (dist[here][i] == 0) //            continue; //        visited[i] = true; //        path.push_back(i); //        ret = min(ret , dp(path, adj + dist[here][i])); //        visited[i] = false; //        path.pop_back(); //    } //    return ret; //} // //int main() { //    ios_base::sync_with_stdio(0); //    cin.tie(0); // //    cin >> N; //    for (int i = 0; i < N; i++) { //        for (int j = 0; j < N; j++) { //            cin >> dist[i][j]; //        } //    } //    vector<int> a; //    int ret = INF; //    for (int i = 0; i < N; i++) { //        a.push_back(i); //        visited[i] = true; //        ret = min(dp(a), ret); //        a.pop_back(); //        visited[i] = false; //    } //    cout << ret << endl; // //    return 0; //}     //동적계획법을 활용한 외판원 순회 #include<iostream> #include<vector> #include<algorithm>   using namespace std;   int dist[16][16]; int cache[16][1<<16]; int N; int INF = 1000000007;   int dp(int here, int start, int visited) {          if (visited == (1 << N) - 1) {         if (dist[here][start] != 0)             return dist[here][start];         else             return INF;     }                   int& ret = cache[here][visited];     if (ret > 0)         return ret;       ret = INF;     for (int next = 0; next < N; next++) {         if (visited & (1<<next) || dist[here][next] == 0)             continue;         ret = min(ret, dist[here][next] + dp(next, start, visited + (1<<next)));     }     return ret; }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> N;     for (int i = 0; i < N; i++) {         for (int j = 0; j < N; j++) {             cin >> dist[i][j];         }     }     int ret = INF;     /*for (int i = 0; i < N; i++) {         ret = min(ret ,dp(i, i, (1<<i)));         cout << ret << endl;     }*/       cout << dp(0,0,1) << endl;       return 0; }     Colored by Color Scripter

cs

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.165~ 167, 317~319.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!