백준 2098 - 외판원 순회; Java

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

2098번: 외판원 순회

 

 

 

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

public class Main {
	static int N;
	static int[][] map;
	static int[][] dp;
	static final int INF = 987654321;
	
	public static int dfs(int cur, int visitBit) {
		if(visitBit == (1<<N)-1) {
			if(map[cur][0] == 0) return INF; 
			return map[cur][0];
		}
		
		if(dp[cur][visitBit] != INF) {
			return dp[cur][visitBit];
		}
		
		for(int i=0;i<N;i++) {
			//i 도시에 방문한 적 없음 && cur -> i에 길 있음
			if((visitBit & (1<<i))==0 && map[cur][i] != 0) {
				dp[cur][visitBit] = Math.min(dp[cur][visitBit], dfs(i, visitBit|(1<<i))+ map[cur][i]);
			}
		}
		
		return dp[cur][visitBit];
	}
	
	public static void main(String[] args)throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		dp = new int[N][(1<<N)-1];
		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.valueOf(st.nextToken());
			}
			Arrays.fill(dp[i], INF);
		}
				
		int result = dfs(0, 1);
		System.out.println(result);
	}

}

 

P 1) 23라인에서 i 도시를 빼줄 때, visitBit | (1<<i)를 해줘야 됨.

처음에 visitBit - (1<<i)로 하였으나, 현재 방문한 도시 중에 i 도시가 없으면 음수가 되어버려서 | 연산으로 해야 됨

 

P 2) INF 를 Integer.MAX_VALUE 로 두면 안됨..

왜 안돼 .. ㅡㅡ^ 이것 때문에 5 틀림 적립 ㄱㅅ