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

1. 문제유형 : DFS(백트래킹)

2. 시간복잡도 : O(N^2)

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


public class Main {

static int N, map[][], answer = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		map = new int[N][N];
		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		delivery(0, 1, 0, 1);
		
		System.out.println(answer);
	}
	
	public static void delivery(int current, int cnt, int total, int flag) {
		if(answer <= total) return;
		
		if(cnt == N) {
			if(map[current][0] != 0) answer = Math.min(answer, total + map[current][0]);
			return;
		}
		for (int i = 1; i < N; i++) {
			if((flag & 1<<i) == 0 && map[current][i] != 0) {
				delivery(i, cnt+1, total+map[current][i], flag|1<<i);
			}
		}
	}
	

}