[BOJ] 백준 [10971] 외판원 순회2 JAVA

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

10971번: 외판원 순회 2

문제

풀이

DFS완전탐색 + 백트래킹 문제이다.
출발도시를 각자 주어진 도시마다 설정해놓고
dfs 재귀호출로 이동할 수 있는 다른 도시들을 완전 탐색을 진행하면서 
만약 모든 도시를 다 탐색 했을 경우 , 방문했던 도시를 다시 방문하지 않은 것으로 백트래킹시켜준다.

모든 도시를 다 탐색했을 경우엔 이때까지 비용들의 총합과 현재 최소비용을 비교하면서 갱신하면 끝

 

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    static ArrayList<Node>[] path;
    static int N,start,min;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //그래프 초기화
        N = Integer.parseInt(br.readLine());
        path = new ArrayList[N];
        visit = new boolean[N];
        for(int i=0;i<N;i++){
            path[i] = new ArrayList<>();
            int[] input = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            for(int e=0;e<input.length;e++){
                if(input[e]==0) continue;
                path[i].add(new Node(e,input[e]));
            }
        }
        //탐색
        int min=Integer.MAX_VALUE;
        for(int i=0;i<N;i++,start=i) dfs(i,0,0);
        System.out.println(min);
    }
 
    private static void dfs(int cur,int depth,int totalCost) {
        visit[cur]=true;
        if(depth==N && cur==start){
            min = Math.min(min,totalCost);
            return;
        }
 
        for (Node next : path[cur]) {
            if(next.node==start&&depth==N-1)
                dfs(next.node,depth+1,totalCost+next.cost);
            else if(visit[next.node]) continue;
 
            dfs(next.node,depth+1,totalCost+next.cost);
        }
        visit[cur]=false;
    }
 
    static class Node{
        int node;
        int cost;
        public Node(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }
    }
}