[백준] 10971 외판원 순회 2 - 백트래킹 + DFS + 외판원 순회 문제(Traveling Salesman Problem (TSP) )JAVA

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

코드설명

백트래킹 + DFS + 외판원 순회 문제(Traveling Salesman Problem (TSP) ) 문제입니다.

 

이 문제에서 처음에는 문제이해가 어려웠습니다.

처음에 이해했을때, 1-. 2-> 3-> 4-> 3-> 2-> 1 로 이동하는 것이라고 생각하였고,

1->2->3->4 로 이동하는방법은 DFS로 찾는다고 가정하여도 4->1 로 갈때 과연 그것이 최단거리를 보장할 수 있는가? 라는 생각이 들었습니다. 그러나 생각해보면 문제에서 한번 방문했던 공간은 다시 돌아갈 수 없기에 4->1로 가는것이 맞습니다. 만약에 4->1로 돌아가지 못한다면 해당 방안은 유효하지 않는 경로입니다.

 

이 문제 같은경우 1->2->3->4->1 로 생각해야합니다.

 

사이클이 존재하는 이유는, 출발지점에서 다시 출발지점으로 돌아와야하기 떄문입니다.

문제의 사이클을 확인해보면,

2->3->4->1->2

3->4->1->2->3

...

위와 같이 결국 경로가 사이클이 존재하여 어디서든 출발하든 결국에는 같은 경로입니다.

 

그렇기에 어디서든 출발하든 값은 같습니다. 즉, 한번만 simulate()를 해주면 답을 찾을 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int answer = Integer.MAX_VALUE;
	public static boolean[] visited;
	public static int[][] graph;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
 
    	graph = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			graph[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	//1 -> 2 -> 3 -> 4 -> 1 
        visited = new boolean[N];
        visited[0] = true;
        simulate(0, 0, 1, 0);
        
    	System.out.println(answer);    	
    }
    
    public static void simulate(int originalStart, int nowIdx, int cnt, int sum) {
    	
    	//모든 경로 다 방문햇을경우 종료시킵니다.
    	if(cnt == N) {
    		if(graph[nowIdx][originalStart] != 0) {
        		answer = Math.min(answer, sum + graph[nowIdx][originalStart]);
    		}   
    		return ;	
    	}
    
    	for(int i=0;i<N;i++) {
    		if(visited[i] == false && graph[nowIdx][i] != 0) {
    			visited[i] = true;
    			simulate(originalStart, i, cnt + 1, sum + graph[nowIdx][i]);
    			visited[i] = false;
    		}
    		
    	}
    }
}