#백준_10971 외판원 순회2 - Java

# 유형 : 탐색

# 조건문만 잘 체크하면 쉽게 해결, 맨 처음에 min 범위를 잘못 지정해서 10%에서 계속 틀려서 로직이 틀린줄 알고 한참 걸렸다. Limit 설정에 신경을 써야한다.. dfs로 탐색을 하여, count가 N개이고, 시작지점과 마지막지점이 같을때 체크해주면 된다.

package bj;

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

public class p10971 {
	static int N;
	static int arr[][];
	static int min=Integer.MAX_VALUE;
	static boolean visit[];
	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++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<N; i++) {
			dfs(i,i,0,0);
		}
		System.out.println(min);
		
	}
	public static void dfs(int start, int i, int cnt, int sum) {
		if(cnt == N && start==i) {
			min = Math.min(min, sum);
			return;
		}
		
		for(int idx=0; idx<N; idx++) {
			if(arr[i][idx]==0)
				continue;
			
			if(!visit[i] && arr[i][idx]>0) {
				visit[i] = true;
				sum += arr[i][idx];
				dfs(start, idx, cnt+1, sum);
				visit[i] = false;
				sum -= arr[i][idx];
			}
		}
		
		
	}
}