외판원순회2

외판원 순회 2

🙋‍♂️ 들어가며

이번 시간에는 외판원 순회 TSP 알고리즘에 대한 문제이다

해당 문제는 순열탐색으로 푼다면 N <= 10 이라서

O(N * N!) 로 풀 수 있다.

흐름은 다음과 같이 진행되겠다

✅ 코드 (순열)

package boj;

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

public class Main {
	static int N;
	static int[][] W;
	static boolean[] visited;
	static int min_cost = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		W = new int[N][N];
		
		for (int r = 0; r < N; r++) {
			String[] cols = br.readLine().split(" ");
			for (int c = 0; c < N; c++) {
				W[r][c] = Integer.parseInt(cols[c]);
			}
		}
		
		
		// 1. 초기값 삽입
		visited = new boolean[N];
		for (int i = 0; i < N; i++) {
			int start = i;
			visited[start] = true;
			back_tracking(start, i, 0, 1);
			visited[start] = false;
		}
		
		// 3. 출력
		System.out.println(min_cost);
	}
	
	
	
	// 2. 순회
	static void back_tracking(int start, int cur, int cost, int cnt) {
		// 2-1. 최대 깊이 도달시
		if (cnt == N) {
			if (W[cur][start] != 0) {
				min_cost = Math.min(min_cost, cost + W[cur][start]);
			}
			return;
		}
		
		// 2-2. 아직 전부 방문 안했다면
		for (int next = 0; next < N; next++) {
			// 만약 방문했거나, 같은 곳을 방문한다면 skip
			if (visited[next] || W[cur][next] == 0) continue;
			
			// 그게 아니라면
			visited[next] = true;
			back_tracking(start, next, cost + W[cur][next], cnt+1);
			visited[next] = false;
		}
		
	}
	
	
	
}

어?? 다시 보니 시간을 줄일 수 있겠다

(N & 2^N) * N

DP + bitmasking + dfs

✅ 코드 (bitmasking + DP)

package boj;

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

import java.util.Arrays;

public class Main {
	static int N;
	static int[][] W;
	static int[][] DP;
	static int INF = Integer.MAX_VALUE;
	static int min_cost = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		W = new int[N][N];
		DP = new int[N][1<<N];
		
		for (int r = 0; r < N; r++) {
			String[] cols = br.readLine().split(" ");
			for (int c = 0; c < N; c++) {
				W[r][c] = Integer.parseInt(cols[c]);
			}
			// 방문하지 않은 상태를 INF로 초기화
			Arrays.fill(DP[r], INF);
		}
		
		// 0번 도시에서 시작
		// 시작도시 방문했다는 표시로 mask=1
		int start = 0;
		dfs(start, 0, 1, 0);
		System.out.println(min_cost);
	}
	
	
	
	
	static void dfs(int start, int cur, int mask, int cost) {
		// 모든 도시를다 방문했다면
		if (mask == (1<<N)-1) {
			if (W[cur][start] != 0) {
				min_cost = Math.min(min_cost, cost + W[cur][start]);
			}
			return;
		}
		
		
		// 가지치기
		if (cost >= DP[cur][mask]) return;
		
		// 그게 아니라면 비용 갱신
		DP[cur][mask] = cost;
		
		for (int next = 0; next < N; next++) {
			// 다음 도시를 방문 안했고, 도시가 다르다면
			if ( (mask & (1<<next)) == 0 && W[cur][next] != 0 ) {
				int next_cost = cost + W[cur][next];
				
				// 비용이 작다면 dfs 진행
				if (next_cost < min_cost) {
					dfs(start, next, mask | (1<<next), next_cost);
				}
			}
		}
		
	}
	
	
	
	
}