[종만북][알고스팟] Traveling Salesman Problem 1(TSP1), 여행하는 외판원 문제 - 완전탐색(BruteForce) JAVA

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

algospot.com :: TSP1

코드설명

완전탐색을 활용합니다.

 

여행하는 외판원 문제를 해결하는 재귀 호출 알고리즘입니다.

여행하는 외판원 문제는 알려졌듯이 모든 도시가 서로 연결되어 있는 상태에서 어떤 도시에서 시작하고, 어떤 경로로 가야 최단거리로 갈 수 있느냐를 구하는 문제입니다.

 

이 문제에서 유의해야할점 입니다.

1. 이 문제 역시 반환 타입을 double로 하며, 평소에 void로 하던 것보다 로직이 더 깔끔합니다.

급하게 풀다보면 void로 전역변수를 손쉽게 초기화하는 방식으로 진행하곤 하는데, 평소에 반환타입을 지키면서 푸는것이 코드가 훨씬 깔끔해지기에, 기분이 좋습니다.

 

이 문제의 시간복잡도는 N * (N-1)! 으로, N! 이 될 것 입니다.

시간복잡도는 O(N!)이 될 것 입니다.

 

만약 N = 10, 도시가 10개라면, 10 * 9! ( 도시의 경로를 선택하는 경우 ) 로 10! 이 될 것 입니다.

10! = 3,628,800 입니다.

 

현재까지는 괜찮지만, N이 더 커지면 시간초과가 발생할 것 이므로, 이후에 TSP를 더 발전시킨 방식으로 포스팅을 더 하겠습니다.

코드

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static double[][] dist;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			dist = new double[N][N];
			
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					dist[i][j] = Double.parseDouble(st.nextToken());
//					System.out.println(dist[i][j]);
				}
			}
			double answer = Double.MAX_VALUE;
			for(int startCityIdx = 0; startCityIdx < N; startCityIdx++) {
				boolean[] visited = new boolean[N];
				visited[startCityIdx] = true;
				answer = Math.min(answer, shortestPath(new ArrayList<Integer>(Arrays.asList(startCityIdx)), visited, 0));
			}
			System.out.println(String.format("%.10f", answer));
		}
		
	}
	
	//path : 지금까지 만든 경로
	//visited : 각 도시의 방문 여부
	//currentLength : 지금까지 만든 경로의 길이
	//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
	public static double shortestPath(ArrayList<Integer> path, boolean[] visited, double currentLength) {
		//기저 사례 : 모든 도시를 다 방문했을 때는 시작도시로 돌아가고 종료한다.
		if(path.size() == N) {
//			return currentLength + dist[path.get(0)][path.get(path.size() - 1)];
			return currentLength;
		}
		double ret = Double.MAX_VALUE; //매우 큰 값으로 초기화
		//다음 방문할 도시를 전부 시도해 본다.
		for(int next = 0; next < N; next++) {
			if(visited[next] == true) continue;
			int here = path.get(path.size() - 1);
			path.add(next);
			visited[next] = true;
			//나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
			double cand = shortestPath(path, visited, currentLength + dist[here][next]);
			ret = Math.min(ret, cand);
			visited[next] = false;
			path.remove(path.size() - 1);
		}
		return ret;
	}
	
}

 

 

코드2. (전역변수를 사용한 코드, ArrayList 사용 대신 인자로 현재 위치를 보낸다.)

가장 큰 차이점은 첫번째 코드는 인자로 currentLength를 모두 더해가며 인자로 계산하는 반면에

저는 상위 재귀호출 함수에서 하위재귀호출이 끝나면 더해가는 방식으로 구현했습니다. 사실 path ArrayList로 visited와 currentLength를 모두 구할 수 있습니다만, 연산속도를 줄이기 위해 (효율적으로 검색하기 위해) 함께 인자로 보냅니다.

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 int C, N, M, H, W;
	public static int answer = Integer.MAX_VALUE;
	public static double[][] matrix;
	public static int[] visited;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			matrix = new double[N][N];
			
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					matrix[i][j] = Double.parseDouble(st.nextToken());
				}
			}
			double answer = Double.MAX_VALUE;
			//시작점은 모든 시작점에서 최저거리를 찾을 것 이다.
			for(int i=0;i<N;i++) {
				visited = new int[N];
				Arrays.fill(visited, -1);
				visited[i] = 1;
				answer = Math.min(answer, getShortestPath(0, i));
			}
			System.out.println(String.format("%.10f", answer));
			
		}
		
	}
	
	public static double getShortestPath(int level, int cur) {
		//처음에 level == N으로 했다가 마지막 return ret = Double.MAX_VALUE이기에 계속해서 최대값이 출력되었었다. 이러한 것들이 사소해보이더라도 모두 로직에 관여한다.
		if(level == N - 1) { // N-1, 즉 시작점을 제외하고 모든 노드를 방문한다면, return 0. 
 
			return 0;
		}
		
		double ret = Double.MAX_VALUE;
		for(int next=0; next<N; next++) {
			if(cur == next) continue;
			if(visited[next] == -1) {
				visited[next] = 1;
				ret = Math.min(ret, getShortestPath(level + 1, next) + matrix[cur][next] ) ;
				visited[next] = -1; //-1로 바꿔줍니다. 처음에 0 으로 했다가 실수.
			}
		}
		
		return ret;
	}
	
}