[백준] 외판원 순회

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

2098번: 외판원 순회

비트마스킹과 DP를 같이 활용해야하는 문제입니다. 먼저, dp[i][j]의 정의는 다음과 같습니다. 현재 i의 조합을 방문하고 현재 j에 왔을 때, 순회를 마치기 위해 필요한 최소 비용이 됩니다. 이 문제의 핵심은 순회를 하기 때문에 어디서 시작을 해도 무방합니다. 저의 경우에는 0번 노드를 시작점으로 두었으므로 visited는 1로 시작을 하게 됩니다. dp 배열의 초기값은 모두 -1로 두어 아직 방문되지 않은 지점들을 의미합니다. 0번 노드를 시작으로 모든 순열의 조합을 탐색하는데 그 과정에서 이미 계산이 되어 있는 값이 있으면 그것을 그대로 활용해주면 됩니다. 

 

package bj;

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

public class Main_2098 {
	static int[][] adj;
	static int[][] dp;
	static int n;
	static final int MAX = Integer.MAX_VALUE / 10;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		
		adj = new int[n][n];
		dp = new int[1 << n][n];
		
		for (int i = 0; i < (1 << n); i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = -1;
			}
		}
		
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				adj[i][j] = Integer.parseInt(st.nextToken());
			}
		}			

		System.out.println(tp(1, 0));	
		
	}
	
	
	static int tp(int visited, int cur) {
		// 모든 지점을 방문한 경우
		if (visited == ((1 << n) - 1)) {
			if (adj[cur][0] == 0) {
				return MAX;
			} else {
				return adj[cur][0];
			}
		}
		
		// 기록되어 있는 값이 있는 경우
		if (dp[visited][cur] != -1) {
			return dp[visited][cur];
		}
		
		// 현재 값을 찾으로 왔으므로 갱신을 해준다.
		dp[visited][cur] = MAX;
		
		for (int i = 1; i < n; i++) {
			// 이동할 수 없는 경우
			if (adj[cur][i] == 0) {
				continue;
			}
			
			// 방문한 지점인 경우
			if (((1 << i) & visited) > 0) {
				continue;
			}

			dp[visited][cur] = Math.min(dp[visited][cur], tp((visited | (1 << i)), i) + adj[cur][i]);
		}
		
		return dp[visited][cur];		
	}
}