BOJ 2098번 외판원 순회

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

github : https://github.com/junho0956/Algorithm/blob/master/2098/2098/%EC%86%8C%EC%8A%A4.cpp

 

BOJ 10971번 외판원 순회2 (https://junho0956.tistory.com/172)을 통해 풀이하였습니다. 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
#define INT_MAX 99999999
 
int arr[16][16];
int dp[16][1 << 16];
int N, visit_check;
 
int TSP(int start, int visit) {
    if (visit == visit_check) {
        if (arr[start][0] == 0) return INT_MAX;
        else return arr[start][0];
    }
 
    int& result = dp[start][visit];
    if (result) return result;
 
    int len = INT_MAX;
    for (int i = 1; i < N; i++) {
        if (arr[start][i] != 0 && (visit & (1 << i)) == 0)
            len = min(len, arr[start][i] + TSP(i, visit | (1 << i)));
    }
 
    return result = len;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> arr[i][j];
 
    visit_check = (1 << N) - 1;
 
    cout << TSP(0, 1);
    return 0;
}