[Java] 백준 17182 우주 탐사선

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

난이도

골드3

문제

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

입력

첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N)
다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij ≤ 1000)

출력

모든 행성을 탐사하기 위한 최소 시간을 출력한다.

내 코드

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

class Main {

    static int N, K, ans;
    static int[][] time;
    static boolean[] visited;
    
    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());
        K = Integer.parseInt(st.nextToken());
        
        time = new int[N][N];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                time[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++) {
                    time[i][j] = Math.min(time[i][j], time[i][k] + time[k][j]);
                }
            }
        }

        visited = new boolean[N];
        ans = Integer.MAX_VALUE;

        visited[K] = true;
        dfs(K, 1, 0);
        
        System.out.println(ans);
    }

    public static void dfs(int now, int depth, int sumTime){
        if(depth == N){
            ans = Math.min(ans, sumTime);
            return;
        }
        
        if (sumTime >= ans) return;

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, depth + 1, sumTime + time[now][i]);
                visited[i] = false;
            }
        }
    }
}

플로이드-워셜 알고리즘

모든 정점에서 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다.
모든 쌍 최단 경로 문제를 해결하는데 사용된다.

for (int k = 0; k < N; k++) { // 경유하는 노드
	for (int i = 0; i < N; i++) { // 출발 노드
    	for (int j = 0; j < N; j++) { // 도착 노드
        	time[i][j] = Math.min(time[i][j], time[i][k] + time[k][j]);
        }
    }
}

i에서 j로 바로 가는 거리와 i에서 k를 거쳐 j로 가는 거리 중 짧은 것을 선택한다.

이를 통해서 최단 거리를 계산해두고 백트래킹으로 문제를 풀면 된다.