[DP] 비트마스킹 외판원 순회

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

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 1000000000

int graph[16][16];
int dp[16][1<<16];
int n;

int trabel(int x, int bit) {
    if( bit == (1 << n) - 1 ) {
        return graph[x][0] != 0 ? graph[x][0] : INF;
    }
    
    if ( dp[x][bit] != -1 ) return dp[x][bit];
    dp[x][bit] = INF;
    
    for (int i = 0; i < n; ++i) {
        if ( graph[x][i] != 0 && !(bit&(1<<i)) ) {
            dp[x][bit] = min( dp[x][bit], graph[x][i] + trabel(i, bit|(1<<i)) );
        }
    }
    
    return dp[x][bit];
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << trabel(0, 1);
    
    return 0;
}

dp 배열은 현재 방문한 장소를 관리, 총 17비트

0번 도시에서 시작하여 0도시로 돌아와야 함

dp[i][bit]는 bit에 속하는 도시에 갔고 현재 i일때 도착하기까지 남은 최소 거리