[백준] 2098 외판원 순회

문제링크 : www.acmicpc.net/problem/2098

2098번: 외판원 순회

어떤 위치에서 출발해서 모든 여행지를 방문하고 마지막엔 다시 원래 위치로 돌아오는 방법 중 가장 짧은 거리를

구하는 문제이다.

 

처음에 문제를 잘못 알아서 모두 방문 후에 원래 위치로 돌아올 때는 여행지를 방문하면서 와도 되는 줄 알았다.

 

그래서 플로이드 워셜로 여행지 간 최소거리를 저장해두고 dfs의 마지막에는 start로 돌아오는 최소 거리를 더해주었었다.

 

하지만 틀렸다. 그냥 마지막 여행지에서 한번에 시작지점으로 와야 풀렸다.

 

또, 내 코드는 1번여행지 ~ N번 여행지에서 출발하는 모든 경우를 돌았다. 이유는 문제의 테스트케이스에서는 3번인가 4번 여행지에서 출발하는 경우만 답이 나오는 것으로 잘못 계산했기 때문이었다. 나중에 다른 사람 풀이와 증명을 확인 해보니 어떤 여행지든 출발지점 딱 한 곳만 확인해주어도 됐더라.

 

어쨌든 dp는 dp[시작지점][현재위치][방문정보] 이며 **(현재위치에서/방문정보에가 이러할 때)** 방문하지 않은 모든 곳을 방문하는 비용은 항상 같음을 보장하기에 메모이제이션이 가능하다. 물론 시작지점은 빼도 된다는 것을 알았으니 

dp[현재위치][방문정보] 만으로도 가능하다.

 

import java.io.*;
import java.util.*;
public class Main {
	public static int N;
	public static int [][]map;
	public static int dp[][][];
	public static int dist[][];
	public static int dfs(int start, int cur, int bitmask) {
		if(bitmask==((1<<N)-1)) {
			if(map[cur][start] != 0) {
				return map[cur][start];
			}
			return 30000000;
		}
		
		if(dp[start][cur][bitmask]!=0) {
			return dp[start][cur][bitmask];
		}
		
		int ret = 30000000;
		for(int i=0;i<N;i++) {
			if(map[cur][i]==0) continue;
			if((bitmask & (1<<i))!=0) continue;
			ret = Math.min(ret,map[cur][i]+ dfs(start,i,bitmask | (1<<i)));
		}
		return dp[start][cur][bitmask] = ret;
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		dist = new int[N][N];
		map = new int[N][N];
		for(int i=0;i<N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int ans = 30000000;
		//dfs
		dp = new int[N][N][(1<<N)];
		for(int i=0;i<N;i++) {
			ans = Math.min(ans, dfs(i,i,(1<<i)));
		}
		System.out.println(ans);
	}

}