[백준] 10971번 외판원 순회 2

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

10971번: 외판원 순회 2

 

 

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

public class Main {

    public static int N;
    public static int[][] arr;
    public static boolean[] visit;
    public static int min = Integer.MAX_VALUE;


    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        arr = new int[N][N];
        visit = new boolean[N];

        for(int y = 0; y < N; y++) {
            st = new StringTokenizer(br.readLine());
            for(int x = 0; x < N; x++) {
            	arr[y][x] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < N; i++) {
            visit[i] = true;
            dfs(i, i, 0, 0);
        }

        System.out.println(min);
    }  

    // start = x, now = y
    public static void dfs(int start, int now, int depth, int sum) {
        // 처음 노드는 main에서 방문했으므로 N - 1
        if(depth == N - 1) {
            // 마지막 노드에서 맨 처음 노드로 가는 비용 계산
            if(arr[now][start] != 0 ) {
                sum += arr[now][start];
                min = Math.min(min, sum);
        	}
        	return;
        }

        for(int i = 0; i < N ; i++ ) {
            if(!visit[i] && arr[now][i] != 0 ) {
                visit[i] = true;
                dfs(start, i, depth + 1, sum + arr[now][i]);
                visit[i] = false;
            }
        }
    }
}