[JAVA/자바 정올 1681] 해밀턴 순환회로

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

JUNGOL

 

풀이

백트래킹, 순열 문제입니다.

회사에서 출발해서 배달 장소들의 순열을 돌고 다시 회사로 도착하므로

 

0 -> 배달지의 순열 -> 0    ( 문제 설명에서는 1을 회사라 소개하지만 코드상 0이 회사입니다) 

이런식으로 구현해서 풀었지만 시간초과가 났습니다.

 

이후 백트래킹 기법을 추가했습니다.

permutation 함수에서 파라미터를 val을 받아서 현재의 배달 비용을 저장하고, 

min_val(조건에 부합하는 최솟값)과 비교를 해줘서 val 크다면 다음 순열로 백트래킹.

import java.io.*;
import java.util.*;


public class Main {
	
	static int[][] map;
	
	static int n , min_val=100000;
	//순열 이용 
	static int[] numbers;
	static boolean[] isSelected;
	
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		n=Integer.parseInt(br.readLine());
		//n이 1이 아닐때
		
		if(n!=1) {
			StringTokenizer st;
			map=new int[n][n];
			// 출발지와 목적지가 회사니까 numbers에 다음 목적지를 저장 
			numbers=new int[n-1];
			isSelected = new boolean[n-1];

			for(int i=0 ; i <n ; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j=0 ; j<n; j++) {
					map[i][j]= Integer.parseInt(st.nextToken());
				}
			}
			
			permutation(0, 0);
			//
			if(min_val==Integer.MAX_VALUE) System.out.println(0);
			else {			
				System.out.println(min_val);
			}			
		}
		// n=1일때 
		else {
			System.out.println(2*Integer.parseInt(br.readLine()));
		}

	}
	// val 백트래킹에 이용 
	// min_val를 기준으로 순열이 돌때마다 val에 이동하기 위한 비용을 더해주며,
	// 최소값보다 커지면 return
	
	// 출발지와 도착지가 회사므로 0->배달 장소의 순열 -> 0 
	private static void permutation(int cnt, int val) {
		// TODO Auto-generated method stub
		if(val>=min_val) return;

		if(cnt==n-1){
            int tmp;
            tmp=map[numbers[n-2]][0];
            if(tmp==0) return;
            min_val=Math.min(val+tmp, min_val);
            return;
            }

		for(int i=0; i<n-1; i++) {
			if(isSelected[i]) continue;
            int plus;
            numbers[cnt]=i+1;
            isSelected[i]=true;
 
            // cnt==0일때 0-> 첫번째 배달장소 
            if(cnt==0) plus=map[0][numbers[0]];
            // cnt!=0일 cnt-1 번째 배달장소 -> cnt번째 배달장소
            else plus=map[numbers[cnt-1]][numbers[cnt]];
            // 배달하지 못하는 상황일땐 백트래킹 
            if(plus==0) plus=100001;
            permutation(cnt+1, val+plus);
            isSelected[i]=false;
		}

	}

}

들여쓰기가 이상하게 나오네요... 코드는 돌려봤는데 이상은 없습니다 !!