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

 

 

문제출저 

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

2098번: 외판원 순회

 

 

 

소스코드

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

public class Main_B_2098_외판원순회 {
	
	static int n;
	static int[][] board;
	
	static int INF;
	static int fullbeat;
	static int[][] dp;

	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		board = new int[n][n];
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		INF = 987654321;
		fullbeat = (1<<n)-1;
		dp = new int[n][fullbeat];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < fullbeat; j++) {
				dp[i][j] = -1;
			}
		}
		
		System.out.println(dfs(0,1));

	}
	
	public static int dfs(int start, int visited ) {
		
		if(visited == fullbeat) {
			if(board[start][0] == 0) return INF;
			else return board[start][0];
		}
		
		if(dp[start][visited] != -1) {
			return dp[start][visited];
		}
		
		dp[start][visited] = INF;
		
		for(int i = 0; i < n; i++) {
			if(board[start][i] == 0 || (visited & (1<<i)) != 0) continue;
			dp[start][visited] = Math.min(dp[start][visited], dfs(i, visited | 1 << i) + board[start][i]);
		}
		
		return dp[start][visited];
	}
}