[백준] 외판원 순회 2098 - JAVA

문제

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

풀이

말그대로 외판원 순회 문제이다.

외판원 순회는 DP + 비트마스킹 + DFS를 이용하여 풀어야 한다. 

시간 복잡도는 O(2^n * n^2) 이므로 N의 크기가 작아야 한다. 따라서, 문제에서도 N의 크기가 15까지 나오는 것이다.

 

dp배열은 다음과 같이 작성해야 한다.

dp[현재 정점][방문한 정점들]

예를들어, 현재 2번정점에 있고 1,2,3을 방문했다고 한다면 dp배열은 dp[2][(1,2,3)] 이 되어야 할것이다. 

그러나, 배열의 index에 1,2,3을 표시할 수 없다. 따라서, 여기서 비트마스킹을 이용해야 한다.

 

예를들어, n=4일때 1,2,3을 방문했다면 0111 이렇게 작성하면 된다.

모두 방문했을때는 1111이 될것이다. 이를 코드로 나타내보면 (1<<4) - 1로 나타내면 된다.

 

이제 문제를 어떻게 접근할지 생각해보자.

1. 모두 다 방문 했을때

    1) 현재 정점에서 1로 가는 길이 없을 경우 끝

    2) 길이 있을 경우, 기존의 작은값과 비교하여 더 작은 값으로 갱신

2. 방문 할게 있을때

    for문을 이용하여 다음 방문할 곳을 결정한다.

    다음 방문할 곳과 이미 방문한 곳을 or 연산을 이용하여 계산한다.

    1) 다음 방문할 곳이 이미 방문한 곳이면 pass

    2) 길이 없으면 pass

    3) dp값이 현재 계산한 값보다 크다면 갱신 후 재귀

        (현재 2에 있고 다음으로 3을 방문할 차례면, dp[3][0111]과 dp[2][0011] + w[2][3] 을 비교)

 

코드

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

public class Main {	 
	
	static int n;
	static int w[][];
	static int dp[][];
	static int visitAll;
	static int answer = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		visitAll = (1<<n)-1;
		dp = new int [n+1][visitAll+1];		
		w = new int[n+1][n+1];
		
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=n;j++) {
				w[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1;i<=n;i++) {
			for(int j=0;j<=visitAll;j++)
				dp[i][j] = Integer.MAX_VALUE;
		}
		
		dp[1][1] = 0;
		visit(1, 1);
		System.out.println(answer);
	}
	
	static void visit(int cur, int visited) {
		//다 방문해서 1로 돌아갈때
		if(visited == visitAll) {
			if(w[cur][1] == 0)
				return;
			answer = Math.min(answer, dp[cur][visited]+w[cur][1]);
			return;
		}
		
		//방문할게 있을때
		for(int i=0;i<n;i++) {
			int next = 1<<i;
			int newVisited = next | visited;
			
			if(newVisited == visited) continue;
			if(w[cur][i+1] == 0) continue;
			
			if(dp[i+1][newVisited] > dp[cur][visited] + w[cur][i+1]) {
				dp[i+1][newVisited] = dp[cur][visited] + w[cur][i+1];
				visit(i+1, newVisited);
			}
		}
	}

}