<Algorithm> 17. 10971번 외판원 순회2

1. 10971번 외판원 순회2

• 이동경로의 가중치를 순열하는 것이 아니고 순회할 지점 순서를 순열로 하여 모든 경로의 값을 확인하여 최솟값을 구한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String[] args) throws NumberFormatException, IOException {
    
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N=Integer.parseInt(br.readLine());
        int[][] w=new int[N][N];
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                w[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        int[] d=new int[N];
        
        for(int i=0;i<N;i++) {
            d[i]=i;
        }
        
        int min = Integer.MAX_VALUE;
        
        do{
            int result = 0;
            boolean check = false;
            
            for(int i=0; i<N-1; i++) {
                
                if(w[d[i]][d[i+1]] == 0) {
                    check=true;
                    break;
                }
                
                result += w[d[i]][d[i+1]]; 
            }
            
            if(!check && w[d[N-1]][d[0]] != 0) {
                
                result += w[d[N-1]][d[0]];
                
                if(result < min) {
                    min = result;
                }
            }
            
        }while(permetation(d));
        
        System.out.println(min);
    }
    
    public static boolean permetation(int[] input) {
        int i=input.length-1;
        int j=input.length-1;
        
        while(i>0) {
            if(input[i-1]<input[i]) {
                break;
            }
            i--;
        }
        
        if(i==0) return false;
        
        while(i<=j) {
            if(input[i-1]<input[j]) {
                int temp=input[i-1];
                input[i-1]=input[j];
                input[j]=temp;
                break;
            }
            j--;
        }
        
        j=input.length-1;
        
        while(i<j) {
        
            int temp=input[j];
            input[j]=input[i];
            input[i]=temp;
            i++;
            j--;
        }
        
        return true;
    }
 
}