J1681. 해밀턴 순환회로

제목

제출 코드

• 사용 알고리즘 : 백트래킹

package jungol;

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

public class J1681_hamiltonianCycle {

	static int N, result = Integer.MAX_VALUE;
	static int[][] arr;
	static boolean[] visit;

	static void go(int n, int from, int sum) {
		if(result <= sum) return;
		if(n==N-1) {
			if(arr[from][0]!=0) result = Math.min(result, sum+arr[from][0]);
			return;
		}

		for(int i=0; i<N; i++) {
			if(!visit[i] && arr[from][i]!=0) {
				visit[i] = true;
				go(n+1, i, sum+arr[from][i]);
				visit[i] = false;
			}
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		arr = new int[N][N];
		visit = new boolean[N];

		for(int i=0; i<N; i++) {
			String[] line = br.readLine().split(" ");
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(line[j]);
			}
		}
		visit[0] = true;
		go(0, 0, 0);

		System.out.println(result);
	}

}