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

1. 문제

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

JUNGOL

2. 접근방법

해밀턴 순환이 되는 최단경로를 구하는 문제

최단경로 하니 처음에 MST나 다익스트라를 생각할 법한데 이 알고리즘들을 이용하기에는 조금 부적합한 면이 있다.

그냥 정점의 갯수가 적으니 백트레킹으로 모든 간선에 대해 다해보면 된다.

 

다만 이미 발견된 총 cost 값보다 가는 도중 cost가 더 커지면 그 가지는 잘라주어야 한다.

3. 풀이

1. 행렬을 입력받고 dfs 돌릴 visit 준비

2. 출발지부터 시작해서 dfs를 돌리며 아직 방문하지 않은 모든 간선에 대해 출발

3. 가는데 필요한 cost 값들을 저장

4. 모든 점을 연결 한 뒤 마지막 점에서 출발점으로 잇기(해당 간선이 없을 수 도 있다.)

5. 위 과정이 정상적으로 돌아간 모든 경우에서 가장 작은 cost값을 찾기

6. cost 출력

4. 자바 코드

package 정올;

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

public class P1681해밀턴순환경로 {
	static int N, matrix[][], cost;
	static int min = Integer.MAX_VALUE;
	static boolean visit[];
	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer  st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		visit = new boolean[N];
		matrix = new int[N][N];
		
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < N ; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		visit[0] = true;
		dfs(0,0,0);
		System.out.println(min);
	}

	static void dfs(int now,int sel,int cost) {
		if(sel == N-1) {
			if(matrix[now][0] == 0)
				return;
			cost += matrix[now][0];
			min = Math.min(cost, min);
			return;
		}
		if(cost>min)
			return;
		
		
		for(int i = 0 ; i < N ; i++) {
			
			if(visit[i])
				continue;
			if(matrix[now][i] == 0)
				continue;
			
			visit[i] = true;
			dfs(i,sel+1,cost+matrix[now][i]);
			visit[i] = false;
		}
	}
}

 

5. 마치며

이것도 MST나 다익스트라로 어떻게 풀어볼까 했지만

결국 N을 작게 준 문제는 그냥 브루트포스로 푸는게 맞는거 같다.