외판원 순회 (TSP)

백준 2098번: 외판원 순회

아이디어

모든 도시를 한 번씩 방문해야 한다. 무조건 첫 번째 도시부터 방문하자. 어차피 모든 도시를 방문해야 하기 때문에 시작하는 도시가 어디인지는 답에 영향을 주지 않는다.
visited에 도시 방문 여부를 표시한다. i번째 마을 방문 여부는 visited&(1<<i)으로, 방문 표시는 visited|(1<<i)로 할 수 있다. 모든 도시를 방문한 경우(Base case) 마지막 도시에서 첫 번째 도시로 이동하는데 필요한 비용을 반환한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[16][16]; // from, to
int dp[16][1<<16]; // current city, visited city list
const int INF = 987654321;

int solve(int cur, int visited) {
    // base case
    if (visited == (1<<N)-1) {
        return arr[cur][0] ? arr[cur][0] : INF;
    }
    
    int &ret = dp[cur][visited];
    if (ret != -1) return ret;
    
    ret = INF;
    for (int i = 0; i < N; i++) {
        if (visited&(1<<i) || arr[cur][i] == 0) continue;
        ret = min(ret, solve(i, visited|(1<<i)) + arr[cur][i]);
    }
    return ret;
}

int main() {
    ios_base::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];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 1);   
    return 0;
}

설명

현재 도시와 지금까지 방문한 도시 목록이 같은 경우 중 가장 비용이 적은 경우를 구해야 한다.
예를 들어, 1 -> 2 -> 3 -> 4 순서로 이동한 경우와, 1 -> 3 -> 2 -> 4 순서로 이동한 경우 둘 다 현재 도시는 4번 도시이고 지금까지 방문한 도시 목록도 1, 2, 3, 4로 같지만 비용은 다르다. 두 경우 중 비용이 더 적은 경우를 구하고, 나중에 재사용하기 위해 memoization한다.

ret = min(ret, solve(i, visited|(1<<i)) + arr[cur][i]);

ret를 레퍼런스로 선언했기 때문에 최솟값이 자동으로 기록된다.

여담

진짜 개어렵다..