외판원 순회 문제

어떤 한 마을에서 다른 마을들을 한 번씩만 방문하여 시작 마을로 돌아올 때, 마을에서 마을로 이동하는 비용의 총합이 최소가 되게 하는 문제이다.

예제 - 백준 2098번 : 외판원 순회

2098번: 외판원 순회

DP + 비트마스킹

$O(N^p)$안에 해결할 수 있는 방법이 아직 발견되지 않았다. N이 작을 경우 DP와 비트마스킹으로 풀 수 있다.

변수 정의

TSP(visited, currentVertex) 정의

TSP를 다음과 같이 정의한다.

<aside> 🚩 현재까지 방문한 (현재 마을 포함) 마을들의 visited와 현재 마을의 번호 currentVertex가 주어졌을 때, 남은 마을들을 모두 방문하여 0번 마을로 돌아가는데 드는 최소비용

</aside>

visited를 비트마스킹으로 정의

visited를 비트마스킹으로 표현한다.

구현 과정

말로 표현하는 것보다 코드를 이해하는게 더 쉽다.

주석을 상세히 작성하였다. 비트마스킹 기법에 대한 설명은 생략하였다.

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define INF 2000000000

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

int n;
int start;
int w[16][16];
int cache[16][65536];

// 마을의 수는 n
// 방문한 상태의 경우의 수는 2^n
// 따라서 n*2^n 가지의 TSP가 존재한다.

int tsp(int current, int visited) {
    // 모든 마을을 방문한 경우
    // 현재마을에서 시작지점까지 가는 길이 있다면
    // 그 비용을 리턴한다.
    if (visited == (1 << n) - 1) {
        return w[current][start] ? w[current][start] : INF;
    }

    // DP
    // 해당 경로의 비용을 이미 계산했다면 리턴한다.
    int &ret = cache[current][visited];
    if (ret != -1) return ret;

    // 방문하지 않은 모든 마을을 순회한다.
    ret = INF;
    for (int i = 0; i < n; i++) {
        // 이미 방문한 경로 무시
        if (visited & (1 << i)) continue;
        // 경로가 없다면 무시
        if (!w[current][i]) continue;
        ret = min(ret, tsp(i, visited | (1 << i)) + w[current][i]);
    }

    return ret;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
        }
    }
    
    cout << tsp(0, 1) << '\\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
}

요약하면 다음과 같다.