[정올]1681_해밀턴 순환회로_Java_ DFS + 백트래킹

 

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

JUNGOL

해밀턴 경로 : 모든 정점 혹은 꼭지점을 한번씩만 지나는 경로

해밀턴 순환 : 시작점과 끝 점이 같은 해밀턴 경로 => 브루트포스로 풀어야함

 

•  n<=10~11 : 브루트포스로 풀어도 됨 O(n!)
•  n<= 12~13 : 브루프토스로 하면 시간넘을 것임 -> 브루트포스 + 백트래킹
•  n<=16~17 : 세우는 식에 따르 지만 보통 DP + bitmasking ->o(2^n +n^2)

 

* 다익스트라  : 모든 정점으로의 최소비용 보장 => 정점을 한번만 방문함을 보장 X ; 최소 신장트리 MST x

 

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

//정올 1681:해밀턴 순환회로
//백트래킹 DFS
public class Main_1681 {
	static int N, min;
	static int Matrix[][];

	public static void dfs(boolean[] visited, int current, int sum, int cnt) { // sum: 직전까지 합한 것
		
		visited[current] = true;

		if (cnt == N ) {// 마지막 장소
			if(Matrix[current][1]==0) {
				return;
			}
			sum += Matrix[current][1];
			if (min > sum) {
				min = sum;
			}
			
			return;
		}
		if(sum>min) {
			return;
		}

		for (int j = 1; j <= N; j++) {
			if(!visited[j] && Matrix[current][j] != 0) {
				sum += Matrix[current][j];
				dfs(visited, j, sum, cnt+1);
				sum -= Matrix[current][j];
				visited[j] = false;
				
			}
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		Matrix = new int[N + 1][N + 1];
		min = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				Matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		dfs(new boolean[N + 1], 1, 0, 1);
		System.out.println(min);
	}

}

https://github.com/LeeJieuni/Algorithm/blob/main/JO/Main_1681.java

GitHub - LeeJieuni/Algorithm