백준 10971 외판원 순회2 (Silver2)

정답 코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int N;
	static int[][] map;
	static boolean[] visited; 
	static int minimum = Integer.MAX_VALUE;
	static int start
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		visited = new boolean[N];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}		
		
        //어디서 출발하는 것이 가장 빠른지 모르기 때문에 일단 다 돌려본다
		for(int i = 0; i < N; i++) {
			visited[i] = true;
			start = i;
			DFS(0,0,0);
			
		}
		System.out.println(minimum);
	
	}
	
	
	public static void DFS(int sum,int node, int depth) {
		
        //모든 도시를 방문하고 나면 종료조건 확인
		if(depth == N-1) {
        	//만약에 마지막 도시에서 처음 도시로 돌아올 수 있다면
			if(map[node][start]!=0) {
            	//최솟값 갱신해준다
				minimum = Math.min(minimum,sum+=map[node][start]);
			}
			return; 
		}
		
		//경로에 따라 Backtracking
		for(int i = 0; i < N; i++) {
			if(!visited[i]&&map[node][i]!=0) {
				visited[i] = true;
				DFS(sum+map[node][i],i,depth+1);
				visited[i] = false;
			}
		}
		
	}
}

전략

• 어떤 노드에서 시작했을 때 가장 빠른지 모르기 때문에 모든 노드에 대해서 DFS를 해야한다

• DFS도중에 가는 경로가 없는 경우 -> (다시 돌아와야 하니까) 이전에 갈 수 있는 경로가 없다면 백트래킹으로 걸러낸다

• 순회하여 자기 자신으로 돌아온 경우에만 cost를 계산해서 최솟값을 구한다

• DFS 세부 조건 처리하는데 시간이 조금 걸렸지만 비교적 쉬웠던 문제