[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int dist[20][20];
int dp[20][1<<16]; // [현재도시][방문한도시]
int N;
 
int solve(int cur, int visited)
{
    // 모든 마을 방문시 
    if(visited == (1 << N) - 1)
    {
        // 0번 마을로 다시 돌아갈 수 있을때 
        if(dist[cur][0] != 0)
        {
            return dist[cur][0];
        }
        // 그 코스는 불가능 하도록 만들기 위해 매우 큰 수를 return
        else
        {
            return 99999999;    
        }
    }
    
    if(dp[cur][visited] != -1)
    {
        return dp[cur][visited];
    } 
    
    dp[cur][visited] = 99999999;
    
    for(int i = 1; i < N; i++)
    {
        // i번째 지역을 방문한 경우 
        if(visited & (1 << i))
        {
            continue;
        }    
        
        // 해당 지역의 비용이 0인 경우 
        if(dist[cur][i] == 0)
        {
            continue;
        }
        
        dp[cur][visited] = min(dp[cur][visited], solve(i, visited | (1 << i)) + dist[cur][i]);
    } 
    
    return dp[cur][visited];
}
 
int main(void)
{
//    freopen("B2098_input.txt", "r", stdin);
    
    cin >> N; 
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> dist[i][j];    
        }
    }
    
    memset(dp, -1, sizeof(dp));
    
    // 0 →1 →2 →3 →4 →0  시작점이 0인 최소비용 루트가 있다고 가정해보자. 이 때 'A원'의 비용이 들었다면, 
    // 2 →3 →4 →0 →1 →2  시작점이 2인 최소비용 루트는 시작점과 관계없이 'A원'의 비용이 든다. 
    cout << solve(0, 1);
    
    return 0;
}