[JAVA][BOJ 2098] 외판원 순회와 비트 연산

문제링크

문제 파악

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개에 저장하기 위해 이진수로 표현해 비트연산한다.

도시	방문 여부	비트 위치
0번 도시	1이면 방문	0001 (1)
1번 도시	1이면 방문	0010 (2)
2번 도시	1이면 방문	0100 (4)
3번 도시	1이면 방문	1000 (8)

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

비트 연산

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

기호	기능	예	연산값
&	AND (A, B 모두 1이어야 1)	(1 & 1 )	1
|	OR (A, B 둘 중 하나라도 1이면 1)	(1 | 0)	1
<<	A를 왼쪽으로 B만큼 비트 이동	(1 << 2)	0001 0010 ----- 0100 = 4
>>	A를 오른쪽으로 B만큼 비트 이동	(8 >> 2)	1000 0010 ---- 0010 = 2

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 을 기준으로 검사하면 계산하지 않은 상태를 구분할 수 없기 때문에 오류가 날 수 있다.

질문