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

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

출력

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

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

2098번: 외판원 순회

 

---

 

굉장히 유명한 문제인 외판원 순회이다. 이 문제를 풀기 위해선 비트마스킹을 이용한 DP문제인 '계단수'와 '할 일 정하기1'을 먼저 풀어보는 것을 권장한다.

 

만약 비트마스킹을 이용한 DP를 잘 모른다면 무작정 풀어보려하기 보단 공부를 해보고 푸는 것을 추천한다. 그리고 이 글도 어느정도 비트마스킹에 대해 안다는 가정하에 작성하겠다.

 

이 문제는 풀기 위해 중요한 3가지 Point가 있다. 

 

1. cycle의 최솟값 구하기

2. 비트마스킹을 통한 Memorization (DP)

3. 재귀

 

    1. cycle의 최솟값 구하기

이는 어렵지 않은 개념으로 다음과 같은 cycle들이 있다 해보자.

 

 4 -> 2 -> 1 -> 5 -> 0 -> 4

 2 -> 1 -> 5 -> 0 -> 4 -> 2

 1 -> 5 -> 0 -> 4 -> 2 -> 1

 

이 3개의 cycle들이 같은 cycle이라는 것을 한눈에 알 수 있을 것이다. 이렇듯 cycle의 최솟값을 구하기위해 맨 앞에 나오는 도시를 0번 도시로 고정하여 풀면 많은 경우의 수를 줄일 수 있다.

 

    2. 비트마스킹을 통한 Memorization (DP)

 비트마스킹을 간단히 설명하자면 내가 0, 1, 3번 도시를 방문했다는 표시를 001011(2)로 하는 것이다. 이를 10진수로 바꾸면 11이 된다.

이렇게 dp라는 2차원 배열을 통해  다음과 같은 규칙으로 Memorization을 한다.

   

       dp[현재 방문 중인 도시][비트마스킹] = 현재 방문 중인 도시에서 출발하여 방문 안 한 나머지 도시들을 전부 방문하여 0번 도시까지 갈 때 필요한 최솟값

 

 ex) dp[3][11] = 0, 1, 3번 도시를 방문했으며 현재 3번 도시에 있을 때, 3번에서 출발하여 남은 도시들을 방문하여 0번 도시까지 갈 때 필요한 최솟값

 

위와 같이 Memorization을 잘 하면 dp[3][11]의 값을 한 번 구한 후, 다음에 dp[3][11]의 값이 또 필요해도 굳이 다음을 계산할 필요가 없어지므로 시간복잡도를 최적화 할 수 있다.

 

여기서 dp[현재 방문중인 도시][비트마스킹]의 값을 비트마스킹에 표시된 도시들을 방문했을때의 최솟값이라고 하면 이해하기 쉬운데 왜 정의를 어렵게 정했냐라는 생각이 들 수 있다. 사실 이건 재귀를 통해 문제를 해결하기 위해 세팅한 것이므로 3번 내용을 보고 이해해야 한다.

 

    3. 재귀

 우리는 비트마스킹이 모든 도시를 다 방문했다는 표시가 될때까지 재귀를 들어갈 것이다. 예를 들면 다음과 같다.

 

                 [3개의 도시가 있는 경우의 dfs 예시]

 

          dp[0][001] -> dp[1][011] -> dp[2][111]

                              -> dp[2][101] -> dp[1][111]

 

1. dp[0][001]의 값을 알기 위해 dp[1][011]과 dp[2][111]의 값을 구해야 한다.

2. dp[1][011]의 값을 구하기 위해 dp[2][111]의 값을 구해야 한다.

3. dp[2][111]의 비트마스킹이 111이기 때문에 재귀를 들어가지 않고 2번 도시에서 0번 도시로 가는 비용을 return한다.

  (왜냐면 cycle이 되기 위해 마지막 도시인 2번 도시에서 첫번째 도시인 0번 도시로 가는 비용을 생각해야하기 때문)

4. dp[1][011]의 값은 'return 받은 dp[2][111]' + '1번 도시에서 2번 도시로 가는 비용' 이 되고 dp[1][011]을 return한다.

5. 같은 방법으로 dp[2][101]를 구해 return하고 dp[0][001] = Math.min(dp[1][011], dp[2][101]) 이 되고 그 값을 return한다.

 

예시와같이 비트마스킹이 전부 채워진 다음부터 비용을 더한 값을 계속 return하고 그 중 최솟값을 고르는 과정을 반복하는 것이다.

 

 

3가지 Point가 어느정도 이해 됐으면 코드를 보고 이해해보자

 

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    static int INF = 1000000000;
    static int[][] dp;
    static int[][] W;
    static int dfs(int pre, int bit){
        //비트마스킹이 다 채워지면 '현재 도시 -> 0번 도시 비용' return
        if (bit == Math.pow(2, n) - 1) {
            if (W[pre][0] != 0) return W[pre][0]; //만약 현재 도시 -> 0번 도시 길이 없으면 INF return
            else return INF;
        }
        if (dp[pre][bit] != -1) return dp[pre][bit]; //만약 계산해 둔 값이 있으면 그 값 사용
        dp[pre][bit] = INF;
        for (int i = 0; i < n; i++){
            if ((bit & (1 << i)) == 0 && W[pre][i] != 0){ // 아직 방문 안 한 도시이면서 도시 사이에 통행이 가능한 경우 재귀
                dp[pre][bit] = Math.min(dp[pre][bit], dfs(i,  bit | (1 << i)) + W[pre][i]);
            }
        }
        return dp[pre][bit];
    }
    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];
        for (int i = 0; i < n; i++){
            StringTokenizer 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];
        for (int i = 0; i < n ; i++)
            Arrays.fill(dp[i], -1);
        System.out.println(dfs(0, 1));
    }
}