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

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030

JUNGOL

---

풀이 방법

N이 작기 때문에 모든 방법을 다 해보는 완전탐색이 가능하다. 따라서 DFS를 이용해 모든 경로를 탐색하며 최소 거리를 구했다. 

시간을 줄이기 위해 구한 최소거리보다 지금 가고있는 거리가 더 크다면, 그 방법은 구하지 않았다. (if(cnt+map[r][i]>=min) continue;)

또한, 마지막으로 방문한 곳 -> 1로 가는 거리를 구할 때 그래프가 연결되어있지 않다면 거리를 구하지 않아야 한다. 

 

자바 코드

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

public class Jungol_1681_해밀턴순환회로 {
	static StringTokenizer st;
	static int N;
	static int[][] map;
	static boolean visited[];
	static int min;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map=new int[N+1][N+1];
		for (int i = 1; i < N+1; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j = 1; j < N+1; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		min=Integer.MAX_VALUE;
		
		// start는 1부터 
		visited=new boolean[N+1];
		dfs(1,0,0);
		
		if (min==Integer.MAX_VALUE) System.out.println(0);
		else System.out.println(min);

	}
	private static void dfs(int r,int cnt,int c) {
		if (c==N-1) {
			// 마지막으로 방문한곳 -> 1 이 연결되어 있을 때 
			if(map[r][1]!=0) {
				cnt+=map[r][1];
				min=min>cnt?cnt:min;
				cnt-=map[r][1];
			}
			return;
		}
		if (r!=1) visited[r]=true;
		for (int i = 2; i < N+1; i++) {
			if(map[r][i]!=0 && !visited[i]) {
				if(cnt+map[r][i]>=min) continue;
				dfs(i,cnt+map[r][i],c+1);
				visited[i]=false;
			}
		}
	}

}