[정올] 1681번: 해밀턴 순환회로 (Java 자바)

문제

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

JUNGOL

 

 

풀이 및 소스코드

 

백트래킹 문제이다.

현재 돌리고 있는 dfs의 합이 기존에 존재하는 최소 합보다 커졌을 때를 종료 조건으로 두었다.

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, sum = Integer.MAX_VALUE;
	static int[][] g;
	static boolean[] v;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine().trim());
		g = new int[n][n];
		v = new boolean[n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				g[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		dfs(0, 0, 0);
		System.out.println(sum);
	}

	public static void dfs(int s, int cnt, int x) {
		if (s > sum) {
			// 기존의 합보다 크다면 더 이상 볼 필요가 없다. 종료
			return;
		}
		if (cnt == n - 1) {
			//모든 장소에 배달을 마쳤다면 cnt는 n-1이 됨.
			//이제 회사로 돌아가는 비용만 더해주면 된다.
			if(g[x][0]!=0) {
				//회사로 돌아가는 길이 있다면 비교 해준다.
				sum = Math.min(sum, s+g[x][0]);
			}
		}
		for (int i = 1; i < n; i++) {
			if(i==x) continue;
			//굳이 같은장소로 이동할 필요가 없으니 컨티뉴 해준다.
			
			if (!v[i]) {
				if (g[x][i] != 0) {
					//방문하지 않은 장소이고, 가는 길이 있다면 경우의 수를 따져준다.
					v[i] = true;
					dfs(s + g[x][i], cnt + 1, i);
					v[i] = false;
					//다시 false로 바꿔줘야한다. 다음 경우의 수에 영향을 끼치지 않도록 !
				}
			}
		}
	}

}