[JO] 1681. 해밀턴 순환 회로

해밀턴 순환회로, A정점에서 시작하여 모든 정점을 최소비용으로 돌아 A정점으로 돌아오는 문제이다.

다른 말로는 TSP, 외판원 순환 문제라고 한다. 이 문제는 다양한 풀이 방법으로 접근 할 수 있지만 N의 값이 12 이하로 주어졌으므로 백트래킹을 이용한 완탐을 사용해보았다. 단, 순열의 완탐을 돌때 첫번째 점(0)을 제외한 N-1개의 순열을 구하고 이때 마지막에 해당하는 점에서 첫번째점(0)으로의 경로가 존재하는 경우 최종답을 확인해주는 방식으로 구해준다. 또한 방문시에 최저값을 갱신할수 있을때만 방문하는 조건을 사용하여 시간을 줄였다.

package jungol;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_jo_1681_해밀턴순환회로 {
 
    static int N;
    static int[][] map;
    static boolean[] visit;
    
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= null;
        
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        visit=new boolean[N];
        
        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());
        }
        
        visit[0]=true;
        answer=Integer.MAX_VALUE;
        perm(0,1,0);
        System.out.println(answer);
        
    } 
    
    static void perm(int cur,int depth, int sum) {
        if(depth==N) {
            if(map[cur][0]==0)
                return;
            
            sum+=map[cur][0];
            
            answer=Math.min(answer, sum);
            
            return;
        }
        
        for(int i=1;i<N;i++) {
            if(visit[i]==false && map[cur][i]!=0 && sum+map[cur][i] < answer) {
                visit[i]=true;
                perm(i,depth+1,sum+map[cur][i]);
                visit[i]=false;
            }
        }
    }
}