문제링크

문제 파악

TSP(Traveling Salesman Problem) 가중치가 있는 단방향 그래프를 가장 작은 비용을 들이면서 순회하는 경로를 구해라!

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 

• 도시 i에서 j로 이동할 수 없는 경우에는 W[i][j]=0이라고 한다

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

접근 방법

DP[현재도시][현재까지 방문한 도시 리스트] = 남은 모든 도시를 경유하는 데 드는 최소 비용

• 남은 도시를 경유하는 데 드는 최소 비용은 DFS로 구현

리스트를 변수 1개에 저장하기 위해 이진수로 표현해 비트연산한다.

예를 들어 3번, 0번 방문시 1001 -> 9 로 표현한다. 

비트 연산

그동안 피해왔던 비트 연산... 

DP[c][v] = Math.min(DP[c][v], DP[i][v | (1<<i)] + W[c][i])

• [v | (1 << i) ] 
  i번째 도시를 방문했다는 사실을 저장한다.
  • 여기서 v가 누적값인데 비트 연산이면 0, 1을 반환하는게 누적값으로 반영이 안되지 않나? 헷갈렸다.
    v가 0101이고, 1번 도시를 방문하려면 [0101 | 0010]이고, 각 자리수마다 OR 연산을 통해 0111로 바뀐다.
    때문에 0, 1, 2 방문했다는 처리가 가능해진다. 
• if ( ( v & (1 << i)) == 0 )
   i번째 도시 방문했다면 (1 & 1) 이므로 1이 나오지만, 방문하지 않았다면 0을 반환한다.
• if (v == (1 << N) -1)
  N만큼 왼쪽으로 비트 이동했으니, 10000(16)인데 -1해서 15면 01111로 모든 도시를 방문했다는 상태를 확인할 수 있다.
• W[c][i] 는 도시 c에서 i로 이동하는 비용

w[i][j] i -> j 도시로 이동하는 비용 저장 배열
dp[c][v] 현재 도시 c, 현재까지 방문한 모든 도시 리스트 v
	앞으로 남은 모든 도시를 방문할 때 드는 최소 비용

for(i -> 0-N)
	for (j -> 0 - 1<<N)
    	DP를 Integer.MAX_VALUE로 초기화

tsp(c,v) 모든 경우의 수 완전 탐색

tsp(c,v)
	if (모든 도시 방문)
    	시작 도시로 돌아갈 수 있다면 return w[c][시작도시]
        없다면 return MAX_VALUE
   
   if (이미 계산한 적이 있다면) return dp[c][v]
   
   for(i -> 0-N)
   	if (방문한 적 없고 갈 수 있는 도시일 때)
    	dp[c][v] = Math.min(dp[c][v], tsp(i, (v|(1<<i))) + w[c][i])
   
   return dp[c][v]

코드 구현

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

public class Main {
    static final int INF = 1_000_000_000;
    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[] row : DP) Arrays.fill(row, -1);

        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());
            }
        }

        System.out.println(tsp(0, 1));  // 시작: 도시 0, 방문 상태: 000...0001
    }

    static int tsp(int cur, int visited) {
        if (visited == (1 << N) - 1) {
            return W[cur][0] == 0 ? INF : W[cur][0];  // 모든 도시 방문 후 출발 도시로 복귀
        }

        if (DP[cur][visited] != -1) return DP[cur][visited];

        int min = INF;

        for (int next = 0; next < N; next++) {
            if ((visited & (1 << next)) == 0 && W[cur][next] != 0) {
                int cost = tsp(next, visited | (1 << next)) + W[cur][next];
                min = Math.min(min, cost);
            }
        }

        return DP[cur][visited] = min;
    }
}

배우게 된 점

1. 비트연산자로 방문 경로 리스트를 변수 1개로 표현하는 방법을 알았따.

2. DP의 초기값을 -1이나 INF나 설정해놓고 검사해야 정확한 체크가 가능하다. 0 을 기준으로 검사하면 계산하지 않은 상태를 구분할 수 없기 때문에 오류가 날 수 있다.

질문