[백준 2098번] 외판원 순회

소스코드

---

#include <iostream>
using namespace std;
 
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))  
 
int n, w[17][17], memo[17][1 << 16];
 
int tsp(int cur, int visited) {
    if (visited == (1 << n) - 1)  // 모두 방문한 경우
        return w[cur][0] ? w[cur][0] : 987654321;
    int &ret = memo[cur][visited];
    if (ret != -1) return ret; // 이미 계산한 값이 있을 경우
    ret = 987654321;
    for (int i = 0; i < n; i++) {
        if (visited & (1 << i)) continue; // i번째 지역을 방문한 경우
        if (w[cur][i] == 0) continue; // 해당 지역이 0인 경우 (자기 지역으로 가는건 비용이 0)
        ret = MIN(ret, tsp(i, visited | (1 << i)) + w[cur][i]); // 현재 지점에서 i지점으로 이동 체크와 비용 가산
    }
    return ret;
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 1 << 16; j++)
            memo[i][j] = -1;
    cout << tsp(0, 1) << '\n';
    return 0;
}