백준 2098.cpp [외판원 순회]

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다.

 

문제

외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.

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

 

출력

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

 

풀이

잘못된 접근 : 이 문제를 처음 봤을 때 최소 신장 트리를 구성하고 사이클을 형성해주면 되는 줄 알았지만 전혀 그렇지 않았다. 최소 신장 트리를 구성해도 도착지점에서 출발지점으로 돌아와야하기 때문에 최소 신장 트리로 사이클을 만들어줘도 그것이 최적해라는 것이 보장되지 않는다.

 

이 문제를 풀기 위해서는 다이나믹 프로그래밍으로 DFS를 최적화해줘야 한다. 또한 각 정점을 방문했는지 확인하면서 메모이제이션 기법을 같이 사용하기 위해서는 다음과 같이 비트마스킹을 사용해야 한다.

int main() {
    int status = 1; // if binary = 0001
    int now = 4;    // if binary = 0100

    /*
    즉 status는 0번 정점을 방문했음을 의미하는 것이고 
    now는 2번 정점을 가리키는 것이다
    */

    if(status & now) cout << "방문한 적 있음\n"; // binary = 0000
    else cout << "방문한 적 없음\n";

    status = 7; // if binary = 0111

    if(status & now) cout << "방문한 적 있음\n"; // binary = 0100
    else cout << "방문한 적 없음\n";
}

// 출력
방문한 적 없음
방문한 적 있음

그냥 visited 배열 같은 것을 활용하면 안될까? 하지만 단순한 배열로는 매번 각 정점에 방문했었는지, 그리고 현재 어느 정점을 방문 중인지 모두 확인하는 것은 어렵고 까다롭다. 차라리 비트마스킹을 사용하면 쉽게 확인할 수 있다.

 

또한 dfs 탐색이 어떤 정점에서 출발해도 상관 없다는 것 또한 중요한 포인트다.

예를 들어

    dist[0][1] -> dist[1][2] -> dist[2][3] -> dist[3][0] 이 최적해라면,

    dist[2][3] -> dist[3][0] -> dist[0][1] -> dist[1][2] 도 최적해이다.

즉 순환 사이클을 가지고 있고 모든 정점을 방문해야 하기 때문에 어디서 출발하던 최적해는 최적해일 수 밖에 없다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

#define INF (int)1e9

int N;                  // N
int dist[16][16];       // 정점 간의 거리
int dp[16][1 << 16];    // DP
int finalStatus;        // 마지막 최종 상태 (1 << N) - 1

int dfs(int now, int status) {                              // 현재 정점 번호와 방문 상태를 받는다
    if(status == finalStatus) return dist[now][0];          // 만약 최종 상태 값과 현재 상태 값이 같다면 모든 정점을 방문한 것이다. 
                                                            // 0에서 시작했으므로 0으로 돌아가는 거리를 반환한다
    if(dp[now][status] != INF) return dp[now][status];      // dp 배열의 값이 초깃값이 아니라면 이미 갱신됐다는 의미이기 때문에 바로 반환한다. 

    int iBit, cost;                         // iBit는 i번째 노드의 bit 표현 값, cost는 dfs의 반환값    
    for(int i = 0; i < N; i++) {            // N개의 노드만큼 반복
        iBit = (1 << i);                    // i번째 노드의 bit 표현 값
        if(status & iBit) continue;         // 이미 방문하고 있는 상태라면 continue 
        if(dist[now][i] == 0) continue;     // 거리가 0이라면 갈 수 없는 노드이다

        cost = dfs(i, status | iBit);       // dfs 호출
        if(cost) dp[now][status] = min(dp[now][status], cost + dist[now][i]);   // 최솟값으로 갱신
    }
    return dp[now][status];                 // dp 값 반환
}

int main() {ios_base::sync_with_stdio(0); cin.tie(NULL);
    cin >> N;
    finalStatus = (1 << N) - 1;             // 최종 상태 값 저장, if (N == 3) => 0111

    for(int i = 0; i < N; i++) {            // input
        for(int j = 0; j < N; j++) {
            cin >> dist[i][j];
        }
    }
    fill_n(dp[0], 16 * (1 << 16), INF);     // dp 배열 INF로 초기화
    cout << dfs(0, 1);                      // dfs 호출, 시작 노드는 0, 방문 상태는 0001
}