문제

https://www.acmicpc.net/problem/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로 가기 위한 비용을 나타낸다.

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

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

예제 입력 1
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
예제 출력 1
35

접근

밑에 있는 알고리즘 분류를 미리 보고 풀어서 그나마 수월하게 접근을 할 수 있었다.
처음에는 비트, 출발점, 도착점 이렇게 세 가지를 각각 저장하는 3차원 배열로 접근을 했었는데 찾아보니까 외판원 순회 문제는 모든 노드를 거쳐서 돌아오면 사이클이 만들어지기 때문에 출발을 어디서 하든 최적해가 같다고 한다. 그래서 출발점은 굳이 저장할 필요가 없었다. 사실 당연한 거긴 한데.... 같은 노드를 잇는 간선이라도 방향이 다르면 비용이 달라진다는 사실 때문에 순회하는 방향이 바뀌면 최적해도 달라질 거라는 착각을 한 것 같다.

그리고 방문하는 정점을 depth로 해서 약간의 dfs도 가미되어 있었다. 비트 마스크로 이미 방문한 노드의 번호들을 관리하고, 아직 방문하지 않은 노드들에 대해서만 dfs 탐색을 통해 비용이 최소화되는 해를 찾는 방식.

구현

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static int[][] W;
    static int[][] dp;
    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];
        dp = new int[N][1 << N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            Arrays.fill(dp[i], -1);
            for (int j = 0; j < N; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(tsp(0, 1));
    }

    private static int tsp(int location, int mask) {
    	// 모든 노드 방문 완료
        if (mask == ((1 << N) - 1)) {
        	// 마지막 노드에서 출발지로 돌아가는 경로가 없는 경우 유효하지 않은 경로이므로 최댓값을 리턴해 해당 경로를 상쇄.
            if (W[location][0] == 0) {
                return 20000000;
            }
            // 출발지로 돌아감
            return W[location][0];
        }

        if (dp[location][mask] == -1) {
            dp[location][mask] = 20000000;
            for (int i = 0; i < N; i++) {
            	// 이미 방문한 노드거나 location에서 i로 가는 경로가 없는 경우에는 skip
                if ((mask & (1 << i)) == (1 << i) || W[location][i] == 0) {
                    continue;
                }
                
                // location에서 다른 노드로 가는 모든 비용 중 최솟값을 dp[location][mask]에 저장
                dp[location][mask] = Math.min(dp[location][mask], tsp(i, mask | (1 << i)) + W[location][i]);
            }
        }

        return dp[location][mask];
    }
}