[JAVA] 정올 1681 해밀턴 순환회로

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=99&sfl=wr_hit&stx=1681 

JUNGOL

 

풀이

 

코드

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

public class Main {	
	static int N;
	static int[][] map;
	static int answer = 10000;
	static boolean[] visit;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visit = new boolean[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());
		}
		
		visit[0] = true;
		dfs(1, 0, 0);
		
		System.out.println(answer);
		
	}
	
	public static void dfs(int cnt, int select, int cost) {
		if(cnt==N) {
			if(map[select][0]==0) return;
			cost += map[select][0];
			if(answer>cost) answer=cost;
			return;
		}
		
		if(cost> answer) return;
		
		for(int i=0;i<N;i++) {
			if(!visit[i] && map[select][i]!=0) {
				visit[i] = true;
				dfs(cnt+1, i, cost+map[select][i]);
				visit[i] = false;
			}
		}
	}

}