백준 2098번: 외판원 순회 (Java)

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

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로 가기 위한 비용을 나타낸다.

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

출력

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

 

---

 

풀이

naive한 TSP 풀이는 O(N!) 시간 복잡도를 가지지만, 비트 dp를 이용하면 O(N^2 * 2^N) 내에 풀 수 있다. 

일단, 시작점을 정해야 하는데, 모든 도시를 방문하는 최단 사이클이 존재한다면 어디서 시작해도 최단 사이클을 찾을 수 있으므로 시작점을 고정해도 된다. 편의상 도시 번호를 0부터 N-1이라 표현하도록 하며, 시작점은 0으로 고정한다.

이차원 int 배열 dp를 다음과 같이 정의한다:

dp[i][mask] := (mask에 해당하는 도시를 방문하고 마지막으로 도시 i를 방문하는 최단 거리)

여기서 mask는 이진수로, i번째 도시를 방문했을 경우 (1<<i)의 자리의 값이 1이며, 방문하지 않았을 경우 0으로 표현한다. 가령, mask == 3이면 0, 1번 도시를 방문한 것이며, mask = 23이라면 0, 1, 2, 4번 도시를 방문한 것이다.

시작점을 0으로 잡았으므로, dp[0][1] = 0이며, mask = 2부터 (1<<N)-1까지 for문을 돌면서 mask 값에 따라 '최종 방문지가 될 수 있는 후보군(cur라 하자.)'을 고르고, mask에서 cur를 방문하지 않은 상황에서의 이진수값 temp를 구하여, temp에 대해 최종 방문지가 될 수 있는 후보군(prev라 하자.)에 대해 dp[cur][mask] = min(dp[cur][mask], dp[prev][temp] + dist[prev][cur])이다. 여기서 dist[prev][cur]는 prev에서 cur까지의 거리를 의미한다.

그러면, dp[1][1<<N-1], ... , dp[N-1][1<<N-1]은 각각 1, ... , N-1번 도시를 마지막으로 방문하여 모든 도시를 방문한 최소 거리가 된다. 저기에서 다시 0번 도시로 돌아와야 하므로 정답

ans = min(dp[i][1<<N-1] + dist[i][0]) (0 <= i < N)이 된다.

 

dist나 dp 초기값을 적당히 큰 값으로 설정해주면 자잘한 예외처리를 안 해줘도 된다.

 

배운 점

dp 내에 비트마스킹으로 처리하는 테크닉은 언젠가 써본 적은 있는데, 이렇게 차근차근 공부한건 처음이다. 이론은 그렇게 특별할 게 없는 느낌인데, 구현이 조금 생소하다. 잘 알아두도록 하자.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final int INF = 100_000_000;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int ans = INF;
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
        int[][] dp = new int[N][1<<N];
        for (int i = 0; i < N; i++ ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 0) map[i][j] = INF;
            }
        }
        
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][1] = 0;
        for (int bitmask = 2; bitmask < (1<<N); bitmask++) {
            List<Integer> visited = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if ((bitmask & (1<<i)) > 0) {
                    visited.add(i);
                }
            }
            for (int cur: visited) {
                int temp = bitmask ^ (1<<cur);
                for (int prev = 0; prev < N; prev++) {
                    dp[cur][bitmask] = Math.min(dp[cur][bitmask], dp[prev][temp] + map[prev][cur]);
                }
            }
        }
        
        for (int i = 0; i < N; i++) {
            ans = Math.min(ans, dp[i][(1<<N)-1] + map[i][0]);
        }
        System.out.println(ans);
    }
}