Baekjoon 2098번 외판원 순회

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
vector<vector<int>> adj, cache;

int dp(int visited, int here){
    // 기저 사례
    if(adj[here][1] && visited == (1<<n)-1)
        return adj[here][1];
    // 메모이제이션
    int& ret = cache[visited][here];
    if(ret != -1)
        return ret;
    // 재귀 호출
    ret = INF;
    for(int next = 1; next <= n; next++)
        if(adj[here][next] && !(visited&(1<<(next-1))))
            ret = min(ret, dp(visited|(1<<(next-1)), next)+adj[here][next]);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    adj.resize(n+1, vector<int>(n+1, 0));
    cache.resize(1<<(n+1), vector<int>(n+1, -1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> adj[i][j];
    int visited = 1;
    cout << dp(visited, 1);
    return 0;
}

주어지는 도시의 개수는 최대 16개로 완전 탐색의 경우 15! 의 시간이 걸리게 된다.

1초 안에 해결하기 위해서는 동적 계획법으로 풀어야 한다. 현재 경로와 방문한 도시를 쌍으로 메모이제이션 하기 위해서는 현재 경로를 비트마스크 기법을 적용하여 정수 형태로 관리하여야 한다.

일반적인 외판원 문제의 형태지만 갈 수 없는 도시(비용이 0일 경우)가 존재한다는 차이점이 있기 때문에 비용을 계산하는 모든 부분에서 해당 경로의 비용이 0인지 검사해주는 비교문이 필요하다.

모든 도시를 순회하여야 하기에 어느 도시를 시작 지점으로 해도 결과는 같으므로, 1번 도시에서 시작한다고 가정하였다.