[BOJ 2098] 외판원 순회

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

TSP 문제로 유명한 외판원순회 문제이다. 해당문제의 경우 n의 범위가 16까지이기 때문에 일반적인 비트배열만 이용하는것이 아니라 비트마스트+DP를 사용하는 문제이다. 

문제를 해결할 때 상태를 보고 지금까지 모든 부분을 다 여행한 경우 (1<<(n+1)-2)번과 비트가 같은경우 자신으로 돌아가게 하였다. 연산자 arr[pos][1]? arr[pos][1] : INF; 는 "맞는가? 맞으면 앞에꺼 아니면 뒤에꺼" 이다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,dp[1<<17][17],arr[17][17],ans;
 
int solve(int state, int pos){
    if(state == (1<<(n+1)) -2){           // 0번 비트는 비워두었음
        return arr[pos][1] ? arr[pos][1] : INF;
    }
    int &ret= dp[state][pos];
    if(ret != -1)
        return ret;
    ret = INF;
    for(int i=1;i<=n;i++){
        if(state&(1<<i))continue;
        if(arr[pos][i] == 0)continue;
        ret = min(ret , solve(state |(1<<i) , i)+arr[pos][i]);
    }
    return ret;
}
 
int main(){
    ans = INF;
    memset(arr,0,sizeof(arr));
    memset(dp,-1,sizeof(dp));
    cin >> n;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >>arr[i][j];
        }
    }
    cout << solve(2,1);
    return 0;
}