외판원 순회 문제 (TSP) (BOJ_2098)

외판원 순회 문제 (Traveling Salesperson Problem) 이란?

 

- 임의의 정점에서 출발해 모든 정점을 모두 거쳐 다시 원래의 정점으로 돌아오는 순회 경로 중 최소 비용을 구하는 문제

 

- 한 번 거쳐간 길은 재방문이 불가하다.

 

- 비트마스크 이용하는 대표 문제

 

 

 

코드 구현 (백준 2098번)

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

public class Main {
	static int MAX = 16*1000000; // ①
	static int n;
	static int[][] map;
	static int[][] dp;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		dp = new int[n][(1<<n)]; // ②

		for(int i=0; i<n; i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for(int i=0; i<n; i++){
			Arrays.fill(dp[i], MAX); // ③
		}

		tsp(0,1); // ④
		System.out.println(dp[0][1]); // ⑤
        br.close();
	}

	private static int tsp(int current_node, int visit){
		// ⑥
		if(visit == (1<<n)-1){
			if(map[current_node][0] != 0)
				return map[current_node][0];
			return MAX;
		}

		// ⑦
		if(dp[current_node][visit] != MAX)
			return dp[current_node][visit];

		// ⑧
		for(int i=0; i<n; i++){
			if((visit&(1<<i))!=0 || map[current_node][i]==0)
				continue;

			int next = visit | (1<<i);
			dp[current_node][visit] = Math.min(dp[current_node][visit], tsp(i,next)+map[current_node][i]);
		}

		return dp[current_node][visit];
	}
}

 

 

 

 

코드 설명

 

1. main 함수 (① ~ ⑤)

public class Main {
	static int MAX = 16*1000000; // ①
	static int n;
	static int[][] map;
	static int[][] dp;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		dp = new int[n][(1<<n)]; // ②

		for(int i=0; i<n; i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for(int i=0; i<n; i++){
			Arrays.fill(dp[i], MAX); // ③
		}

		tsp(0,1); // ④
		System.out.println(dp[0][1]); // ⑤
        br.close();
	}
}

① MAX 의미?

    MAX값의 용도는 다음의 두 가지이다.

    1) dp[][] 계산했는지 확인용도   

    2) 길이 없는 경우- 최소비용에 영향끼치지 않기 위한 최대 결과값으로 리턴하는 용도

 

② dp[][] 의미?

    dp[현재위치][방문현황] : 이렇게 방문했고, 현재위치에서의 최소 비용을 의미한다.

    dp[][] 배열의 범위 : dp[현재위치][방문현황]-> 현재위치:0~n-1(n개), 방문현황:2^n개

 

③ 왜 dp[][]을 초기화시키나?

    dp[][] MAX값으로 초기화-> dp[][]가 계산됐는지 체크용도로 사용하기 위해서

    즉 dp[][]!=MAX : 계산O (초기화값이 아니므로) 을 의미한다.

 

④ tsp(0,1); //시작점 0으로 설정 + 시작점0 방문했으니까 visit=1

 

⑤ System.out.println(dp[0][1]);

    dp[0][1]: 방문현황 1일 때, 현재위치0에서의 최소비용

    즉 1->(다른 도시들)->1 을 행할 때의 최소비용을 의미하므로, '외판원의 순회에 필요한 최소 비용'을 의미한다.

 

 

 

2. tsp 함수 (⑥ ~ ⑧)

private static int tsp(int current_node, int visit){
	// ⑥
	if(visit == (1<<n)-1){
		if(map[current_node][0] != 0)
			return map[current_node][0];
		return MAX;
	}

	// ⑦
	if(dp[current_node][visit] != MAX)
		return dp[current_node][visit];

	// ⑧
	for(int i=0; i<n; i++){
		if((visit&(1<<i))!=0 || map[current_node][i]==0)
			continue;

		int next = visit | (1<<i);
		dp[current_node][visit] = Math.min(dp[current_node][visit], tsp(i,next)+map[current_node][i]);
	}

	return dp[current_node][visit];
}

⑥ 모든 도시를 방문한 경우

    (1<<n)-1 : 0번째 도시를 제외한 모든 도시를 방문했음을 의미

    그러므로 visit==(1<<n)-1는 모든 도시를 방문했고, 처음 시작점으로 돌아가는 길만 남았을 때를 의미한다.

    이때 map[current_node][0]==0 이라면,

    현재도시->시작점0 으로의 길이 없다는 것이므로 최종결과인 최소비용에 영향을 끼치지 않는 MAX값을 리턴

 

⑦ 이미 최소비용을 계산한 경우

    dp[current_node][visit]==MAX 라면, 현재위치에서의 최소비용이 계산되지 않았다는 것이다.

    dp[current_node][visit]!=MAX는 현재위치에서의 최소비용이 계산되었으므로 계산할 필요가 없음! 

    그 최소비용(dp[current_node][visit])을 리턴한다.

 

⑧ 모든 도시를 방문했거나, 이미 최소비용이 계산된 경우가 아니라면 : 이부분에서 최소비용을 계산한다.

    i번째 도시를 방문했거나, 현재도시->i번째 도시로의 길이 없을 경우 : 넘어간다. (continue)

 

    next : i번째 도시를 방문했을 때의 방문현황을 의미

 

    현재 방문현황에서 현재위치에서의 최소비용 (dp[current_node][visit])

      = '현재 방문현황에서 현재위치에서의 최소비용'과

          '현재위치->i번째로 이동한 비용 + i번째 도시를 방문했을 때의 최소비용' 中 최소값