[알고리즘] 정올 1681 해밀턴 순환회로 - 자바

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=1681 

JUNGOL

 

[풀이 코드]

package day0224;

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

public class JUNGOL_1681_해밀턴순환회로 {
	static int N;
	static boolean[] visited;
	static int[][] array;
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
		visited = new boolean[N];
		array = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		visited[0] = true; // 첫번째 출발지점은 박아두고 시작하기! 
		dfs(0, 0);
		System.out.println(min);
	}
	
	static void dfs(int start, int distSum) {
		if(distSum > min) // 기존 min값보다 크다면 아래 조건문에 들어갈 필요가 없지
			return;
		
		if(visitCheck()) { 
			if(array[start][0] != 0) { // 다 방문하고 집에 올때도 이동비용이 0인 경우가 있네..
				distSum += array[start][0];
				min = Math.min(min, distSum);
			}
			return;
		}
		
		
		for(int i=0; i<N; i++) {
			if(!visited[i] && array[start][i] != 0) { //이동을 못하는 경우(0일때)는 제외해야지..문제 좀 읽자
				visited[i] = true;
				dfs(i, distSum + array[start][i]);
				visited[i] = false;
			}
		}
	}
	
	static boolean visitCheck() { // visited 탐색
		for(int i=0; i<N; i++) {
			if(!visited[i])
				return false;
		}
		return true;
	}
}

• 백준의 외판원 순회 2 문제와 거의? 똑같은 문제라서 복습도 되고 좋았던 문제
• 메인에서 dfs를 시작하기 전에 꼭 visited[0]을 해서 첫 번째 출발지점을 고정시킨 채로 시작해야 한다. 입력 예시의 N이 5개라면 처음 출발지점을 빼고 4개로 순열을 돌려야 했다. 
  예를 들면 {1, 2, 3, 4, 5}의 집합에서 1은 고정한채로 {2,3,4,5}, {2,3,5,4}, {2,4,3,5}... 이런 식으로!
• 또 이 문제를 풀 때 놓치기 쉬운 부분이 이동을 못하는 경우(0)가 있다. 이 부분은 조건문 통해 걸러주기!
  
  
• if(distSum < min) 이 없으면 마지막 테스트 케이스를 시간제한 때문에 통과 못한다! 기존의 갱신된 min값 보다 작은 합은 사전에 return 시켜버리면 된다.