[JUNGOL] 1681. 해밀턴 순환회로

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

JUNGOL

 

 

1. L=0부터 시작할 시 종료 조건은 L==(N-1)이 되어야 한다. 정점은 0 ~ N-1번까지 있기 때문.

 

2. 재귀로 dfs(L, from, total)를 호출하는 것은, L번째까지 계산한 total값을 같이 넘기는 것이다. 따라서 종료조건이 L==N이 되어선 안된다. N번째 무게까지 더해진 무게는 함수를 호출할 때 이미 계산되었다.

 

3. 모든 배송지를 탐색한 후 다시 회사로 돌아와야 하기 때문에, 마지막 배송지에서 회사까지 길이 있는지 확인해야 한다. (map[from][to]==0인지 확인)

 

4. visited 배열의 시작지점도 true로 체크하고 dfs 호출하는거 잊지 말기

 

 

import java.io.*;
import java.util.*;
// 210322

public class Main_JO_1681_해밀턴순환회로 {
	static int N, min;
	static int[][] map;
	static boolean[] v;
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	static void dfs(int L, int from, int total) {

		if (total >= min) return;
		if (L==(N-1)) { // 정점은 0~N-1번까지 있음
			if(map[from][0]==0) return;
			min = Math.min(min, total+map[from][0]);
			return;
		}
		
		for(int to=0; to<N; to++) {
			if(v[to]) continue;
			if(map[from][to]==0) continue;
			
			v[to] = true;
			dfs(L+1, to, total+map[from][to]);
			v[to] = false;
		}
	}
	
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input_JO_1681_해밀턴순환회로.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = stoi(br.readLine().trim());
		min = Integer.MAX_VALUE;
		map = new int[N][N];
		v = new boolean[N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
			for(int j=0; j<N; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		
		v[0] = true;
		dfs(0, 0, 0);
		System.out.println(min);
		br.close();
	}
}