[백준] 10971 외판원순회2

문제보기

import java.util.*;
public class Main
{
  // N제한이 10 : 10! 대략 360만 -> 브루트포스 오키!
  public static int min;
  public static int n;
  public static int[][] map;
  public static int[] arr;

  // 방문하는 도시를 순서대로 쭉 모두 구할것임. 그 중에 제일 작은걸 출력할것임
  // 다음 순열을 구해주는 메서드
  public static boolean next_perm(int[] arr){ // 다음순열 문제 참고
    int i = arr.length - 1;

    while( i > 0 && arr[i-1] >= arr[i]){
      i--;
    }
    if( i <= 0 ){
      return false;
    }

    int j = arr.length-1;
    while(arr[j] <= arr[i-1] ){
      j--;
    }

    int temp = arr[j];
    arr[j] = arr[i-1];
    arr[i-1] = temp;

    int k = arr.length-1;
    while( i < k ){
      temp = arr[k];
      arr[k] = arr[i];
      arr[i] = temp;
      i++;
      k--;
    }
    return true;
  }

  // 비용 계산하는 메서드
  public static int calc(int[] arr){
    int res = 0;
    
    for(int i = 1 ; i < arr.length ; i++ ){
      if(map[arr[i-1]][arr[i]] == 0){ // 비용이 0이면 갈 수 없는곳이 포함되었으므로 불가능한 배열이다 
        return -1;
      }
      res += map[arr[i-1]][arr[i]];
    }
		
    // 마지막에 첫 도시로 돌아와야 한다고 했다. 따라서 이것도 불가능한 경로일 수 있는지 확인해야함
    if(map[arr[arr.length-1]][arr[0]] == 0) return -1; 
    // 가능하다면 이것도 비용에 넣어주자 
    res += map[arr[arr.length-1]][arr[0]]; 
    return res;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    map = new int[n][n];
    arr = new int[n];

    for(int i = 0 ; i < n ; i++){
      for(int j = 0 ; j < n ; j++ ){
        map[i][j] = sc.nextInt();
      }
      arr[i] = i;
    }

    // 각 행렬의 성분은 100만 이하, 가능한 도시갯수는 10개 이하이므로 최댓값은 9백만이다 (귀찮아서 그냥 크게 잡음)
    min = 1000000000; 
    do{
      int temp = calc(arr);
      if(temp == -1){ // 갈 수 없는 경로가 포함된 경우는 다음 순열 구해서 continue..
        continue;
      }
      if(temp < min){ // 최소비용이라면 min 에 넣는다 
        min = temp;
      }
    }while(next_perm(arr));

    System.out.println(min);
  }
}