백준 2098번

문제 해설이 아닌 풀이하면서 거쳐간 생각들을 기록하는 글입니다.

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

접근 과정

TSP 문제가 꽤나 유명해서 그런지 이곳 저곳에서 왜 연산의 수가 많아지고 이를 효율적으로 해결하기 위한 해답을 여러번 본 적이 있다. 그러한 기억을 살려 처음으로 TSP를 해결하는 코드를 구현하는데 비트플래그를 사용한 DP를 적용하였다. DFS를 구현하듯 그래프를 탐색하되 32비트 정수중 16개의 비트로 16개 도시의 방문여부를 나타내는 방식이다. 16개의 비트로 표현된 방문 여부는 캐싱된 배열의 인덱스로 사용하여 메모이제이션을 적용할 수 있게 해준다. 원리만 이해하면 적용하기는 어렵지 않을 것이다. 다만 도시의 수가 너무 많다면 비트 플래그를 사용한 메모이제이션은 적용하기가 힘들 것으로 보인다.
어떤 출발점에서든 순회를 완료할 수 있으므로 출발점은 큰 문제가 되지 않는다. 처음 구현할 때는 이를 생각하지 못하여 함수 시그니처를 travel(start, visited, cur)와 같이 작성하였다. 당연히 travel(visited, cur)과 같이 작성하는 것 보다 메모이제이션을 위한 메모리 사용량도 늘어나고 구현도 비교적 복잡하고 속도도 느렸다. 문제를 풀 때 주어진 문제를 최대한 단순한 문제로 만들도록 신경써야겠단 생각이 들었다.

소스 코드

#include <cmath>
#include <cstring>
#include <iostream>

const int inf = 100000000;

int n;
int graph[16][16];
int cache[1 << 16][16];

int travel(int visited, int cur) {
    if (visited == ((1 << n) - 1)) {
        if (graph[cur][0] != 0) {
            return graph[cur][0];
        }
        return inf;
    }

    int& ret = cache[visited][cur];
    if (ret != -1) {
        return ret;
    }

    ret = inf;
    for (int next = 0; next < n; ++next) {
        if ((visited & (1 << next)) || graph[cur][next] == 0) continue;

        visited = visited | (1 << next);
        ret = std::min(ret, travel(visited, next) + graph[cur][next]);
        visited = visited & (~(1 << next));
    }

    return ret;
}

int main() {
    std::memset(cache, -1, sizeof(cache));
    std::cin >> n;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> graph[i][j];
        }
    }
    
    std::cout << travel(1, 0);
    return 0;
}