[BOJ] 외판원 순회

[BOJ] 외판원 순회

Problem URL : 외판원 순회

#include <algorithm> 
#include <iostream>
#define INF 1e9
#define MAX 16

using namespace std;

int map[MAX][MAX];
int dp[MAX][1 << MAX];//비트마스크, i번째 도시에 방문여부에 따라 i번째 비트를 1(방문),0(미방문)으로 표현
int n;

int tsp(int current, int visited) {
    //현재 도시와 방문한 도시들이 같으면 dp 값이 0이 아니다.
    if (dp[current][visited] != 0)
        return dp[current][visited];
    if (visited == (1 << n) - 1) {
        // 마지막 도시에서 처음 도시로 갈 수 있는지 확인
        return dp[current][visited] = map[current][0] ? map[current][0] : INF;
    }
    int ret = INF;
    for (int i = 0; i < n; i++) {
        // 갈 수 있고 (map 값이 0이 아니고), 방문한 적이 없으면 방문하도록 한다.
        if (map[current][i] != 0 && !(visited & (1 << i)))
            ret = min(ret, map[current][i] + tsp(i, visited | (1 << i)));
    }
    return dp[current][visited] = ret;
}

int main(void) {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
    }
    cout << tsp(0, 1);
    return 0;
}