[백준] 2098 외판원순회

문제보기

외판원순회는 외판원순회2와 다 같은데 N값만 좀 더 커진 문제이다.
2의 경우 N의 최댓값이 10이라서, 모든 경우의 수에 대해 다 해줘도 최대 10! = 약 360만 밖에 안되서 모든 경우의 수를 다 구해줘도 괜찮다. (나는 순열로 풀었다)

하지만 이번 문제는 N의 최댓값이 16이기 때문에 16!은 약 20조… 안된다.
그래서 DP로 접근해주었다.
d[s][e][visit] 에서 s는 시작노드, e는 도착노드, visit은 여태까지 방문한 노드를 비트로 표현한것이며 그때의 최소거리를 저장하게 된다.
N은 최대 16이므로 이 배열의 크기는 최대 4byte * 16 * 16 * 2^16 = 64MB 로 주어진 조건내에서 해결 가능합니다.

자세한 내용은 주석으로 봅시다~!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	static int n;
	static int[][][] d;
	static int[][] prices; 
	static int ip(String s) { return Integer.parseInt(s); };
	
	// DP - Top Down 방식
	// 시작노드 s, 도착노드 e, 방문도시가 visit 일때의 최소거리를 반환하는 함수
	static int go(int s, int e, int visit) {
		// 저장된 것이 있다면 사용합시다 
		if(d[s][e][visit] != 0) {
			return d[s][e][visit];
		}
		
		// 저장된것이 없다면.. ans는 최댓값으로 대충 지정 
		int ans = 1000000*n;
		
		// s와 e사이에, 임의의 도시 i가 있을 때 
		// 이 i가 방문한 도시 리스트에 있으면 
		// d[s][e][visit] 은 d[s][i][visit에서 e제외] + prices[i][e] 중 최솟값과 같아집니다.

		for(int i = 0 ; i < n ; i++) {
			// i는 s, e와 달라야하며 이동가능해야합니다(가중치가 0이면 갈 수 없는 길이라고 주어졌습니다.
			if(i == s || i == e || prices[i][e] == 0) continue; 
			// i는 visit에 있는 도시여야 합니다 
			if((visit & (1 << i)) == (1 << i)) {

				ans = Math.min(ans,  go(s, i, visit - (1 << e)) + prices[i][e]); // 최솟값을 취합니다
			}
		}
		
		// 메모이제이션을 통해 연산 수를 줄여줍시다 
		d[s][e][visit] = ans;
		return ans;
	}
	
	
     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = ip(br.readLine());
    	prices = new int[n][n];
    	
    	for(int i = 0 ; i < n ; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for(int j = 0 ; j < n ; j++) {
    			prices[i][j] = ip(st.nextToken());
    		}
    	}
    	
    	d = new int[n][n][(int)Math.pow(2, n)];
 		
		// 중간에 경유없이 두 도시를 직접적으로 잇는 경우는 prices에 있는 값을 그대로 가져와도 됩니다 
    	for(int i = 0 ; i < n ; i++) {
    		for(int j = 0 ; j < n ; j++) {
    			d[i][j][1 << i | 1 << j] = prices[i][j];
    		}
    	}
    	
    	int min = 1000000*n;
    	
		// 시작도시는 0, 도착도시도 0 으로 두고 풉니다(어차피 루프라서 뭐가 기준이어도 상관은 없어요)
		// 0으로 되돌아오기 직전의 도시를 i 로 두고, 방문도시는 모두 다 선택을 해줍니다.
		// 이 중 최솟값을 찾아주면 정답이 됩니다. 
    	for(int i = 1 ; i < n ; i++) {
    		if(prices[i][0] == 0) continue; // 경로가 없다면 패스 
    		int dist = go(0, i, (int)(Math.pow(2, n))-1) + prices[i][0]; // 마지막도시에서 첫도시로 돌아오는 값도 더해줍니다
    		if(dist < min) min = dist;
    	}
		// 정답 출력 
    	System.out.println(min);
    	
     }
}