[Java] 백준 2098 외판원 순회

2098 외판원 순회 문제 링크

외판원 순회 : Traveling Salesman problem (TSP)

• 조합 최적화(Combinatorial Optimization) 문제로 유명하다.
• 모든 도시를 정확히 한 번씩 방문한 뒤 처음 위치로 돌아오는 최단 경로를 찾는 알고리즘

🤓 생각해봐야 할 부분

1. 알고리즘 : DFS + DP + 비트마스킹

(1) DFS : 도시를 방문하는 모든 경우의 수를 구해야 함
(2) DP : 시간을 줄이기 위해서 계산의 반복을 줄임

• 왼쪽 경로의 경우, 1->2->3->5->4->1
• 오른쪽 경로의 경우, 1->3->2->5->4->1
• 5->4->1가 겹치는 걸 확인 할 수 있음
• 이런 경우 5->4->1의 값을 처음에 구했을 때 미리 저장해두고 나중에 꺼내서 쓸 수 있는 방법은 없을까? -> DP

(3) 비트마스킹 : 각 경로에 대한 값 저장을 효율적인게 할 수 있도록 도움

• visited[] 배열을 사용해서 풀이해도 로직상 문제될 건 없음
• But, 비트마스킹을 활용하면 배열이 아니라 int를 사용하기 때문에 메모리 효율성에서 큰 차이가 남
• 또한, 계산 측면에서 배열 안에서 정수 계산을 하는 것과 정수 안에서 비트 계산을 하는 건 속도 효율성 차이가 큼

2. 출발 도시 설정

Q. 모든 도시를 한 번씩 방문해서 출발지로 돌아오는 문제. 그렇다면 모든 도시를 출발지 설정하여 N번 검사해줘야 할까?

• 결론 : 아님
• 어떤 도시에서 출발하든, 모든 도시를 돌고 다시 출발했던 도시로 돌아오는 과정에서 사이클이 생김
• 따라서, 경로가 같다면 출발점이 어디든 최소 비용은 같음
  ex) 1->2->3, 2->3->1, 3->1->2 모두 같음

3. dp 설정

dp[curr][visit]

• curr : 현재 위치한 도시
• visit : 지금까지 방문한 도시들의 집합 (비트마스크)
• dp[curr][visit] : 방문 표시되지 않은 도시들을 방문하고, 돌아오는 경로의 최소 비용

Code

package forStudy.month04;

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

public class BOJ_2098 {
	static int N;
	static int[][] map;
	static int[][] dp;
	static final int INF = 16_000_000;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		StringTokenizer st;
		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());
			}
		}
		
		dp = new int[N][(1<<N)-1];
		for(int i=0; i<N; i++) Arrays.fill(dp[i], -1);
		
		System.out.println(dfs(0, 1));
		
	}

	private static int dfs(int now, int visit) {
		// 모든 도시를 방문함
		if(visit == (1<<N)-1) {
			// now->0으로 가는 경로가 없는 경우, 최솟값이 되지 않도록 큰 더미값을 넣어버림
			if(map[now][0] == 0) return INF;
			return map[now][0];
		}
		
		// 현재 노드가 방문한 적이 있는 곳이면 저장했던 값을 내보냄
		if(dp[now][visit] != -1) return dp[now][visit];
		// 값 초기화
		dp[now][visit] = INF;
		
		for(int i=0; i<N; i++) {
			// (visit & (1<<i)) == 0 -> 해당 목적지를 방문하지 않은 상태일 때
			// map[now][i] != 0 -> 해당 경로가 존재하는 지
			if((visit & (1<<i)) == 0 && map[now][i] != 0) {
				// dfs(i, visit | (1 << i)) -> i도시로 이동해서, 남은 도시들을 모두 방문하고 다시 0번으로 돌아가는 최소 비용
				// map[now][i] -> 현재 도시(now)에서 i도시로 가는 데 드는 비용
				// 경로가 확정이 된 뒤에 돌아오면서 갈 때와, 올 때 값을 모두 구해서 최솟값을 갱신하는 방식
				dp[now][visit] = Math.min(dfs(i, visit | (1 << i)) + map[now][i], dp[now][visit]);
			}
		}
		
		return dp[now][visit];
		
	}
}