[문제] 정올 1681번 해밀턴 순환회로

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

JUNGOL

내 풀이

 

백트래킹

 

public class Main {
	static int[][] matrix;
	static int N;
	static int ans;
	static boolean[] visited;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());	// 배달 장소 수
		
		matrix = 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++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		ans = Integer.MAX_VALUE;
		visited= new boolean[N];
		
		dfs(0,0,0);
		System.out.println(ans);
		
	}
	static void dfs(int idx, int cnt, int distance) {
		// 거리가 이전에 갔던 것보다 크면 x
		if(distance>=ans) return;
		
		if(cnt == N-1) {
			// **조건**: idx -> 회사까지 올 수 있는지 확인해야 함!! 이거 땜에 계속 틀렸음!!!!!
			if(matrix[idx][0]!=0) {
				int temp = distance + matrix[idx][0];
				ans = Math.min(ans, temp);
			}
			return;
		}
		
		// 백트래킹. 0번은 어차피 회사니까 고려 필요 x
		for(int i=1;i<N;i++) {
			// 방문하지 않은 노드 && idx번 노드에서 갈 수 있는 노드에 대하여,
			if(!visited[i] && matrix[idx][i]!=0) {
				visited[i] = true;
				dfs(i, cnt+1, distance + matrix[idx][i] );
				// 다시 되돌려주기
				visited[i] =false;
			}
		}
	}
}