외판원 순회

외판원 순회

외판원 순회란?

여러 지역을 돌면서 물건을 판매해야 하는 판매원이, 모든 지역을 돌고 다시 출발점으로 돌아와야 한다고 할 때, 가장 최적의 경로를 찾는 문제

즉 출발점이 어디에서든 같은 최단 경로를 도출한다는 의미이다.
통상적으로 첫 번째에서 시작하여 첫 번째에서 끝이 난다.

브루트 포스

만약 N이 20이라고 가정해보자
가능한 모든 경우의 수는 20!이 될 것이고 이것은 충분히 시간초과 날 숫자이다.

다이나믹 프로그래밍

즉 이전의 최소값을 사용한 다이나믹 프로그래밍으로 최적화를 해야한다.
하지만 생각해야 할 것은 경우의 수가 엄청 많다는 것이다.

N = 4일 때
1 번째에서 2번째로 갈 최소 경로를 찾는다고 했을 때
1 -> 2로 바로 갈지
1 -> 3 -> 2
1 -> 3 -> 4 -> 2
1 -> 4 -> 3 -> 2 등등 경우의 수가 많다.
이러한 것을 DP로 사용하려고 할 때 bitmask를 사용한다.

방문한 노드를 bitmask하여 모든 경우를 메모리제이션하는 것이다.

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

public class Main {
	static int N;
	static int[][] dp;
	static int MASK;
	static int[][] graph;
	
	public static void main(String[] args) throws IOException {
		//BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());	
		
		N = Integer.parseInt(st.nextToken());
		MASK = (1 << N) - 1;
		dp = new int[N][MASK + 1];
		graph = new int[N][N];
		
		for (int row = 0; row < N; row++) {
			st = new StringTokenizer(br.readLine());	
			for (int col = 0; col < N; col++) {
				graph[row][col] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int row = 0; row < N; row++) {
			for (int col = 0; col < MASK + 1; col++) {
				dp[row][col] = Integer.MAX_VALUE;
			}
		}
		
		System.out.println(recursion(0, 0));
	}

	static int recursion(int cur_node, int bitmask) {
		if (dp[cur_node][bitmask] != Integer.MAX_VALUE) {
			return dp[cur_node][bitmask];
		}
		
		if (bitmask == MASK - 1) {
			if (graph[cur_node][0] == 0) return 100_000_000;
			return graph[cur_node][0];
		}
		int MAX_NUM = 100_000_000;
		for (int new_node = 1; new_node < N; new_node++) {	
			if (graph[cur_node][new_node] == 0) continue;
			if ( (bitmask & (1 << new_node)) > 0 ) continue;
			int new_bit = (bitmask | (1 << new_node));
			
			MAX_NUM = Math.min(MAX_NUM, recursion(new_node, new_bit) + graph[cur_node][new_node]);
		}
		
		dp[cur_node][bitmask] = MAX_NUM;
		return MAX_NUM;
	}
}