외판원 순회 - 2098

//2098 - 외판원 순회
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 200000000
 
int N;
int arr[16][16];
vector<vector<int>> cache;
 
void init()
{
    cin >> N;
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<N; ++j)
            cin >> arr[i][j];
    cache = vector<vector<int>>(1<<N, vector<int>(N, -1));
}
 
int dp(int visited, int before)
{
    if(visited == (1<<N) - 1)
        if(arr[before][0])
            return arr[before][0];
        else
            return INF;
    
    int& ret = cache[visited][before];
    if(ret != -1)
        return ret;
    ret = INF;
    for(int i = 0; i<N; ++i)
        if(!(visited & (1 << i)) && arr[before][i])
            ret = min(ret, dp(visited | (1<<i), i) + arr[before][i]);
    return ret;        
}
 
int main()
{
    init();
    cout << dp(1, 0);
}

 

 

 

 

 

 

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

2098번: 외판원 순회

 

 

 

 

 

 

외판원 순회

비트마스크를 사용한 DP로 풀었습니다!

최소 순회경로는 어느곳에서 시작을 해도 똑같이 나오는 성질을 이용했습니다!

https://www.acmicpc.net/board/view/29929