[백준 2098번] [DP / 비트마스킹] 외판원 순회

Approach

완전 탐색하기에는 16!의 가능성을 모두 탐색해야하므로 TLE가 날 수 밖에 없다. 

사실 잘 생각해보면, 중복되는 연산이 상당히 많다는 것을 알 수 있다. 예를 들어 1 3 2 4 순서로 방문을 하든, 1 2 3 4 순서로 방문하든

뒤의 방문하는 순서가 동일하다고 하면 뒤에 비용은 완전히 동일하다.  따라서 DP를 활용하면 시간 복잡도를 줄일 수 있다. 어느 마을을 현재 망문했는지 정보가 필요하므로 DP 식에 방문 정보가 필요하게 된다.

 

DP[i][visited] : visited만큼의 마을을 방문하고 현재 i번쨰 마을에 위치해 있다고 했을 때 , TSP 최소비용

 

이 과정에서 visited를 vector로 관리해도 되지만, 비트마스킹을 활용해서 쉽게 어느 마을을 방문했는지 알 수 있다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

int dp[16][1 << 16];
int n;
int cost[16][16];
const int MAX = 987654321;

int dfs(int x, int visited){
    int &ret = dp[x][visited];
    if(ret != -1) return ret;

    if(visited == (1 << n) - 1){
        if(cost[x][0] == 0) return MAX;
        else return cost[x][0];
    }

    ret = MAX;
    for(int i = 0; i < n; i++){
        if((visited & (1 << i)) && (cost[x][i] == 0)) continue;
        ret = min(ret, dfs(i, (visited | (1 << i))) + cost[x][i]);
    }
    return ret;
}


int main(void){
    fastio;
    memset(dp, -1, sizeof(dp));
    cin >> n;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> cost[i][j];
        }

    }
    cout << dfs(0, 1) << "\n";
    return 0;
}