2098 - 외판원 순회

문제: boj.kr/2098
날짜: 09/16 (월)
성공여부: X

 

외판원 순회(TSP)는 n개의 도시가 있고 각 도시를 이어주는 길과 각 길에 대한 비용이 있을 때 외판원이 모든 도시를 돌아 다시 출발한 도시로 돌아오는 최소 비용을 구하는 문제이다.

 

DP의 대표적인 문제임은 알고있었으나, 결국 어떻게 푸는지 몰라 실패했다.

 

 

완전 탐색

가장 먼저 생각해볼 수 있는 알고리즘이다. N이 16이다.

 

모든 도시가 서로 이어져있다고 가정하고 한 도시 중 하나를 골라 출발하여 그 도시를 제외하고 나머지 도시를 고르고 또 나머지 도시를 고르고 ... 이를 반복하여 총 16개 도시를 전부 돌고 다시 처음 도시로 돌아오는 경우의 수는

16C1 * 15C1 * 14C1 * ... * 1C1 * 1C1(처음 도시로 돌아감) = 16!이다.

너무한 숫자

 

16!의 값은 터무니없이 큰 값임을 위의 사진을 통해 알 수 있다.. 그럼 이 경우의 수를 최대한 줄여야한다. 그러기 위해서 경우의 수를 조금 분석해보자. 예를 들어 7개의 도시가 있고 1에서 출발했다고 하자.

 

1 → 2 → 3 → 4 → 5 → 6 → 7 → 1

 

처음에 해당 경로로 외판원이 순회를 마쳤다. 그리고 나서 다음 경로로 이동을 했다.

 

1 → 2 → 3 → 4 → 7 → 5 → 6 → 1

 

7 → 5 → 6 → 1로 이동한 것은 위의 경우와 다르게 이동했으나 이 전에 경로인 1 → 2 → 3 → 4 이동은 사실 처음 이동한 경우와 겹친다! 그럼에도 불구하고 한번 더 방문하여 괜히 힘을 낭비하고 있다. 

 

외판원이 처음 경로로 순회를 하고서 지도에 1 → 2 → 3 → 4로 가는 비용의 총합을 적어두고 두 번째 경로로 이동할 때 1 → 2 → 3 → 4 경로는 스킵하고 4번째 도시부터 7 → 5 → 6 → 1 경로로만 이동하면 힘을 아낄 수 있을텐데 말이다.

 

바로 이때 문제풀이에 DP의 메모이제이션을 사용한다는 힌트를 얻을 수 있다. 꽤 큰 힌트를 얻었다! 

 

 

DP로 접근하자!

그럼, 이제 각 경로의 순서별로 비용의 총합을 저장해두고 활용하면 중복되는 경로가 꽤 없어지므로 경우의 수가 많이 줄어들 것 같다. 하지만, 꼭 경로의 순서별로 비용의 총합을 저장해야할까?

 

이를 알아보기 위해 1 → 2 → 3 → 4 → 5 → 6 → 7 → 1 경로를 좀 더 분석해보자. 사실 이 경로는 2 → 3 → 4 → 5 → 6 → 7 → 1 → 2 경로와 총합이 같고 3 → 4 → 5 → 6 → 7 → 1 → 2 → 3 경로와 총합이 같다.

 

즉,

1 → 2 → 3 → 4 → 5 → 6 → 7 → 1 == 2 → 3 → 4 → 5 → 6 → 7 → 1 → 2 
== 3 → 4 → 5 → 6 → 7 → 1 → 2 → 3 == ... 
== 7 → 1 → 2 → 3 → 4 → 5 → 6 → 7

 

이다! 이 말은 즉, 내가 어떤 도시에서 출발을 하든 결국 최소 비용으로 가는 경로는 모두 같은 경로라는 점이다.

 

이런 생각을 갖고 아래 두 경우의 수를 보자.

1 → 2 → 3 → 4 → 7 → 5 → 6 → 1 

2 → 3 → 4 → 7 → 5 → 6 → 1 → 2

 

두 번째 경우에서 만약 내가 4 도시에 있을 때 1, 2, 3 도시를 거쳐왔다고 해보자. 그럼 2 → 3 → 4 → ... → 1 → 2 경로라서 순서가 상관있어 보이지만 그냥 1부터 출발했다고 보면 1 → 2 → 3 → 4 이므로 뒤에 7 → 5 → 6에 대한 총합만 구해주고 1 도시로 돌아가면 첫 경우와 같다!!! 즉, 내가 방문한 것이 최소 비용의 경로라면 방문의 순서가 상관이 없다는 뜻이다.

 

그럼, 나는 이 경로를 저장할 때 방문의 순서 상관없이 그저 어떤 도시를 방문했는지만 표시하면 된다! 이를 표시하기 위해서 visited 배열, 집합 등 여러가지가 있겠지만 여기서는 연산의 속도를 더더욱 줄여보기 위해 비트마스킹 기술을 사용한다. 총 16개의 도시이므로 16개의 비트에 각각 1, 2, 3, 4, 5, 6, ..., 16 도시로 보고 0 또는 1로 방문 표시를 하는 것이다.

 

그럼 마지막으로 남은 의문은 DP에 어떻게 저장하는가이다. 여기서 좀 이해하는데 애를 먹었지만 위의 설명을 잘 보았다면 이해할 수 있을 것이다. 현재 위치에서 지나온 도시들에 대한 총합을 DP에 저장해야하니까 위의 경우 4에서 1 → 2 → 3 → 4까지의 합을 DP에 저장한다고 하면 dp[4][00...1111] = sum; 이 됨을 알 수 있다. 그럼 1차원 배열에는 도시의 개수 n, 2차원 배열에는 2^n-1 만큼의 크기가 필요함을 알 수 있다. 즉, DP[n][2^n-1] 으로 DP 배열을 선언한다.

 

위의 사실을 모두 이해하면 어느정도 시행착오 끝에 아래 코드를 작성할 수 있을 것이다.

 

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int n;
    static int[][] w;
    static int[][] dp;
    // Math.min 사용을 위해 Integer.MAX_VALUE;로 초기화하면 안된다.
    // if (visited == (1 << n) - 1) 해당 조건에서 갈 수 없다면 최댓값을 주어 해당 값이 최소값으로 갱신되지 않도록 하는데,
    // 리턴된 Integer.MAX_VALUE 값이 int cost = tsp(i, visited | (1 << i)) + w[here][i]; 여기서 더해지기 때문에 Overflow가 발생한다.
    // 그래서, 나는 16개의 도시를 빙 돌면 총 17개의 도시를 방문하는데 각 길의 비용 최대값이 100만이므로 1700만 + 1을 최댓값으로 설정해주었다.
    static int inf = 17000001;

    static int tsp(int here, int visited) {
        if (visited == (1 << n) - 1) return (w[here][0] != 0) ? w[here][0] : inf;
        if (dp[here][visited] != 0) return dp[here][visited];

        dp[here][visited] = inf;
        for (int i = 0; i < n; i++) {
            if ((visited & (1 << i)) != 0) continue;
            if (w[here][i] == 0) continue;
            int cost = tsp(i, visited | (1 << i)) + w[here][i];
            dp[here][visited] = Math.min(cost, dp[here][visited]);
        }

        return dp[here][visited];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        w = new int[n][n];

        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++)
                w[i][j] = Integer.parseInt(st.nextToken());
        }

        dp = new int[n][(1 << n) - 1];
        System.out.println(tsp(0, 1));
    }
}