[백준] 우주 탐사선 - Java 17182

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

 

 

플로이드-워샬 알고리즘과 백트래킹을 사용해서 풀었다.

 

우선, 모든 노드의 최단 거리를 `플로이드-워샬` 알고리즘을 사용해 구해준다.

 

그 후, 백트래킹으로 모든 경우의 수를 탐색하여 나올 수 있는 최대값을 계산한다.

 

public class BOJ17182 {
    static int[][] grid;
    static int N;
    static int K;
    static boolean[] visited;
    static int result = Integer.MAX_VALUE;
    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());
        K = Integer.parseInt(st.nextToken());

        grid = 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++){
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int k = 0; k < N; k++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);
                }
            }
        }


        visited[K] = true;
        dfs(K,0);

        System.out.println(result);
    }

    public static void dfs(int idx, int sum){
        boolean compare = false;

        for(int i = 0; i < N; i++){
            if(!visited[i]){
                compare = true;
                visited[i] = true;
                dfs(i, sum + grid[idx][i]);
                visited[i] = false;
            }
        }

        if(!compare){
            result = Math.min(result, sum);
        }
    }
}