[정올] 1681번. 해밀턴 순환회로 (java, MST)

시작지점으로 돌아가는 최소 거리를 찾아야 하므로 모든 경우를 살펴봐야되서 dfs + 백트래킹으로 풀면된다.

 

모든 지점을 모두 방문할 수 있는 경우는 많은데 그 중 시작지점인 1로 돌아올 수 있고

이미 구했던 답보다 새로 구한 전체 방문 거리가 더 작다면 갱신해준다. 

 

중간에 구한 거리가 이미 구한 거리를 넘어가는 순간도 return처리를 해줘서 시간 초과를 막아줘야한다.

 

 

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

public class Main {
	static int n;
	static int cost[][];
	static boolean vis[];
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		cost=new int[n][n];
		for (int i = 0; i < n; i++) {
			String str=br.readLine();
			StringTokenizer st=new StringTokenizer(str);
			for (int j = 0; j < n; j++) {
				cost[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		// 출발지점은 1이다.
		vis=new boolean[n];
		vis[0]=true;
		go(1,0,0);
		System.out.println(answer);
	}
	private static void go(int cnt, int cur,int sum) {
		if(sum>answer)return;//시간 초과 통과하는 방법
		if(cnt==n) {
			//시작지점으로 돌아가는 방법이 있을 때
			if(cost[cur][0]!=0 && answer>sum+cost[cur][0]) {
				answer=sum+cost[cur][0];
			}
			return;
		}
		for (int i = 1; i < n; i++) {
			if(cost[cur][i]==0 || vis[i])continue;
			vis[i]=true;
			go(cnt+1,i,sum+cost[cur][i]);
			vis[i]=false;
		}
	}
}