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

문제 링크: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030

JUNGOL | 해밀턴 순환회로 > 문제은행

1. 주의할 점

- 완탐으로 하지 않고 백트레킹을 사용한다 (TSP 알고리즘을 사용한다)

- 입력받은 배열의 가중치가 0인 경우, 가중치가 0이 아닌 경로가 없는것이다.

 

2. 구현

- TSP() 함수에 현재 이동한 거리 Sum과 현재 Node인 Now를 매개변수로 전달한다

- Li 리스트를 통해 현재 방문한 점을 따로 구할 수 있다 (선택 사항)

- 아직 방문하지 않았고, Arr[][]값이 0이 아니라면 해당 Node를 방문하는 방식으로 진행한다

- For문을 전부 수행하고, Finish를 확인하는 For문을 수행하면서 Finish가 True면 모든 Node를 방문했다는 의미. 이때, 현재 Node에서 1로 돌아가는 Node가 존재해야 한다. 2가지 모두 만족했다면 Result와 비교하여 Result를 갱신한다

 

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

public class Jungol_1681_해밀턴순환회로 {
	static int arr[][],num,result;
	static boolean visit[];
	static List<Integer> li;
	static void TSP(int sum, int now) {
		for(int i=1;i<=num;i++) {
			if(visit[i] || arr[now][i]==0) continue;
			visit[i]=true;			
//			li.add(i);
			TSP(sum+arr[now][i],i);
			visit[i]=false;
//			li.remove(li.size()-1);
		}
		boolean finish=true;
		for(int i=1;i<=num;i++)
			if(!visit[i]) {
				finish=false;
				break;
			}
		if(finish && arr[now][1]!=0) 
			result = Math.min(result, sum+arr[now][1]);
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine().trim());
		arr = new int[num+1][num+1];
		visit = new boolean[num+1];
		li = new ArrayList<Integer>();
		result = Integer.MAX_VALUE;
		for(int i=1;i<=num;i++) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str);
			for(int j=1;j<=num;j++) 
				arr[i][j] = Integer.parseInt(st.nextToken());
		}
		visit[1]=true;
//		li.add(1);
		TSP(0,1);
		System.out.println(result);
	}
}