BOJ 2098번: 외판원 순회

문제 링크

TSP(Traveling Salesman Problem)이라고 불리는 유명한 문제이다. NP-Complete의 대표적 문제로 아직 다항 시간 내에 해결할 수 있는 알고리즘이 없다! 모든 경로를 순열로 만들어 일일이 탐색한다면 $O(n!)$의 시간이 소요되는데 이 문제에서는 시간 초과가 발생한다. 다이나믹 프로그래밍을 이용하면 시간 복잡도를 줄일 수 있다.

정점 집합 $V$의 부분집합 $S$와 정점 $j(j \neq 0)$에 대하여, $C(S, i)$를 다음과 같이 정의하자.

$C(S, j)$ : 집합 $S$의 정점을 한 번씩 모두 방문하고 정점 $i$에서 종료되는 경로의 최소 비용

이때 구하고자 하는 답은 다음과 같다.

$answer = \displaystyle\min_{i \in V, i \neq 0 }{[C(V, i) + dist(i, 0)]}$

초깃값은 다음과 같이 설정할 수 있다.

$C(\{0\}, 0) = 0$
For $i \neq 0$, $C(\{0, i\}, i) = dist(0, i)$

이 값은 아래와 같이 계산될 수 있다.

$C(S, j) = \displaystyle\min_{i \in S, i \neq j}{[C(S - \{i\}, j) + dist(i, j)]}$

C++로 문제를 해결할 때, $C(S, j)$의 중 집합 $S$를 별도의 vector로 저장하게 되면 시간 혹은 메모리 초과가 발생할 수 있는데, 문제 조건에서 $|V| \le 16$임을 확인하고 16개의 bit로 포함 여부를 표시한다면 $S$를 정수 자료형으로 나타낼 수 있다. 예를 들어, $|V| = 4$일 때 9를 이진수로 표현한다면 1001인데 이는 $S = \{0, 3\}$을 의미한다. 이러한 방식으로 $C(S, j)$의 값을, $|S| = 2$부터 $|V|$까지 순회하고, 그 결과를 std::map<std::pair<int, int>, int> 꼴로 저장하면 $O(n^2 log{n})$의 시간 복잡도로 문제를 해결할 수 있다.

// BOJ 2098. 외판원 순회

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

const int INF {99999999};
int n;

// costs[i][j] is cost to navigate from vertice i to j.
std::vector<std::vector<int>> costs;

// Let C(S, i) be a minimum cost when visiting set of vertices S and terminates at vertice i.
// dp[x] is minimum cost where x.first == (an integer encoding for S) and x.second == i.
std::map<std::pair<int, int>, int> dp;

// Encode string representation of set S to integer.
// For example, when S == {1, 0, 0, 1}, and s == "1001", it returns 9(==1001(2)).
int encode_set(std::string s) {
    int x {0};
    for (int i=0; i<s.size(); i++) x += (1 << (s.size() - 1 - i)) * (s[i] == '1');
    return x;
}

// solve(size) is a process of getting C(S, j) for each vertice j != 0 in S,
// where |S| = size using dynamic programming.
void solve(int size) {
    if (size == 2) {
        // A path consists of one edge.
        for (int i=0; i<n; i++)
            dp[std::make_pair((1 << (n - 1)) + (1 << (n - i - 1)), i)] = costs[0][i];
        return;
    }
    std::string s = std::string(n - size, '0') + std::string(size - 1, '1');
    do {
        // "1" + s is subset of given size, where subset[0] == 1.
        std::string subset = "1" + s;
        // Disallow to return to vertice 0.
        dp[std::make_pair(encode_set(subset), 0)] = INF;
        // For any vertice j != 0 in subset S, get C(S, j) from partial answers C(S - {j}, i).
        for (int j=1; j<subset.size(); j++) {
            if (subset[j] == '0') continue;
            // C(S, j) == min(C(S - {j}, i)) + cost(i, j) where vertice i != 0 is in set S - {j}.
            subset[j] = '0';
            int sub_answer {INF};
            for (int i=1; i<subset.size(); i++) {
                if (subset[i] == '1')  {
                    sub_answer = std::min(
                        sub_answer, dp[std::make_pair(encode_set(subset), i)] + costs[i][j]
                    );
                }
            }
            subset[j] = '1';
            // Store answer of subproblems into map for reuse.
            dp[std::make_pair(encode_set(subset), j)] = sub_answer;
        }
    } while (std::next_permutation(s.begin(), s.end()));
}

int main() {
    // Input
    std::cin >> n;
    for (int i=0; i<n; i++) {
        costs.push_back(std::vector<int>());
        for (int j=0; j<n; j++) {
            int x;
            std::cin >> x;
            if (x == 0) x = INF;
            costs[i].push_back(x);
        }
    }
    // Solve
    dp[std::make_pair(0, 0)] = 0;
    for (int size=2; size<=n; size++) solve(size);
    int answer {INF};
    for (int i=1; i<n; i++)
        answer = std::min(answer, dp[std::make_pair((1 << n) - 1, i)] + costs[i][0]);
    // Output
    std::cout << answer << std::endl;
    return 0;
}