[BOJ] 외판원 순회

#include<iostream>
#include<algorithm>
#define inf 987654321
using namespace std;

int n,all;
int cost[17][17];
int dp[17][1<<17];

int tsp(int cur, int stat){
    
    /*
     모든 정점을 다 방문했을 경우
     */
    if( stat == all )
        // 현재 cur 위치에서 돌아가야할 1위치로 가야하기 때문에
        // cost[cur][1]을 Return
        return cost[cur][1];
    
    int& ret = dp[cur][stat];
    if( ret != 0)
        return ret;
    
    ret = inf;
    for(int i=1; i<=n; i++){
        // 2개의 조건문 이해하기
        // 1. 다음 방문 위치가 방문한 상태인지 Check
        // 2. 현재위치에서 다음위치로 갈 수 있는지 Check
        if(( ( stat & ( 1 << (i-1) )) != 0 ) || cost[cur][i] == 0)
            continue;
        int value = cost[cur][i] + tsp(i, ( stat | (1 << (i-1)) ) );
        ret = min(ret, value);
    }
    return ret;
}

int main(){
    cin >> n;
    all = ( 1<< n ) - 1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            scanf("%d",&cost[i][j]);
    
    cout << tsp(1,1) << endl;
    return 0;
}