chapter6 : 여행하는 외판원 문제(완탐)

문제

NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다. 이 문제를 다항 시간에 해결할 수 있는 방법은 현재까지는 존재하지 않지만, 도시의 숫자가 작은 경우에는 비교적 사용 가능한 시간 안에 문제를 해결할 수 있다.

AOJ 에서 이 문제는 같은 내용을 가진 문제 여러 개로 구성된다. 문제 번호에 비례해 도시의 개수가 올라가므로, 뒤로 갈수록 더욱 효율적인 방법을 써야 해결할 수 있다.

도시의 수 N <= 8 이라고 할 때, 여행하는 외판원 문제를 해결하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어진다. 각 테스트 케이스의 첫 줄에는 도시의 수 N (3 <= N <= 8) 이 주어진다. 그 후 N 줄에, 각 N 개씩의 실수로 도시간의 거리가 주어진다. 도시들은 1 부터 N 까지의 숫자로 표현되며, i 번째 줄의 j 번째 실수는 i번째 도시와 j번째 도시 사이의 거리이다. 각 거리는 0 이상 1415 이하이고, 소수점 밑 열 자리까지 주어진다.

주어진 행렬은 대칭이며, 입력되는 거리들은 삼각 부등식 (triangle inequality) 을 만족한다고 가정해도 좋다.

출력

테스트 케이스마다 한 줄에 최소 경로의 길이를 소수점 밑 열 자리까지 출력한다. 1e-7 이하의 절대/상대 오차가 있어도 맞는 답으로 인정한다.

예제 입력

2
3
0.0000000000  611.6157225201  648.7500617289
611.6157225201  0.0000000000  743.8557967501
648.7500617289  743.8557967501  0.0000000000
4
0.0000000000  326.0008994586  503.1066076077  290.0250922998
326.0008994586  0.0000000000  225.1785728436  395.4019367384
503.1066076077  225.1785728436  0.0000000000  620.3945520632
290.0250922998  395.4019367384  620.3945520632  0.0000000000

예제 출력

1260.3657842490
841.2045646020

 

코드1 (실패 -> 통과)

음.. 사실 지금은 어디서 문제인지 잘 모르겠다..
모든 경로의 경우의 수를 구한 뒤 최소값을 찾는 것인데..
getResult에서 파라미터 x는 인덱스를 가르킨다.
path에
0 -> 1 -> 2
0 -> 2 -> 1
1 -> 0 -> 2
1 -> 2 -> 0
2 -> 0 -> 1
2 -> 1 -> 0
순으로 모든 경우를 탐색하고
기저사례에서 값을 더하여 반환한다.

문제를 찾았다!
static double minVal = Double.MAX_VALUE;
이 녀석을 매번 케이스 마다 초기화를 해줬어야 됐는데 ....빼먹었던 것이 문제였다.

이로직이 나는 더 간단하고 좋다.

 

코드2 (통과)

시작점을 인자로 넣어주고 해당 시작점에서 가장 최솟값을 찾아 반환한다.

import java.util.*;
import java.io.*;  
import java.math.*;
public class Main { 
  
  static int N;    
  static double[][] map;
  
  
  public static double getResult( Stack<Integer> path, boolean[] visited, double currentLength) { 
    
    // 기저 사례  
    if ( path.size() >= N ) return currentLength;
    
    double ret = Double.MAX_VALUE; 
    for ( int next = 0; next < N; ++next ) {
      
      if ( visited[next] ) continue;
      int here = path.peek();
      path.add( next );
      visited[ next ] = true;
      ret = Math.min( ret, getResult( path, visited, currentLength + map[ here ][ next ] ) );
      visited[ next ] = false;
      path.remove( path.peek() );
      
    }
    
    return ret; 
  }
  
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringBuilder sb   = new StringBuilder();
    StringTokenizer st = null;
    
    int C = Integer.parseInt( br.readLine() );
    while ( C --> 0 ) {
      
      // 입력값 셋팅 및 초기화
      N = Integer.parseInt( br.readLine() );
      map = new double[N][N];  
      
      for ( int i = 0; i < N; ++i ) {
        String[] str = br.readLine().split("  ");
        for ( int j = 0; j < N; ++j ) map[i][j] = Double.parseDouble( str[j] );
      }
      
          Stack<Integer> path = new Stack<>();
          boolean[] visited = new boolean[N];
          
          double ans = Double.MAX_VALUE;
          for ( int i = 0; i < N; ++i ){
            
            path.push( i );
            visited[i] = true;
            
            double res = getResult( path, visited, 0.0 );
            ans = Math.min( ans, res );
            
            visited[i] = false;
            path.pop();
            
          }
          
          sb.append( BigDecimal.valueOf(ans).setScale(10, RoundingMode.HALF_UP) ).append("\n"); 
    }
      
    bw.write( sb.toString() );
    bw.flush();
    bw.close();
    br.close(); 
  }  
  
} 

문제

https://algospot.com/judge/problem/read/TSP1

algospot.com :: TSP1

비고

https://madplay.github.io/post/the-need-for-bigdecimal-in-java

자바 BigDecimal: 정확한 실수의 표현과 부동 소수점