아이디어

• 경로 내에 행성이 중복되도 상관 없다고 하였으므로, 우선 두 행성 간의 최단거리를 모두 구하자.
  • $N \le 10$이므로 시간복잡도 $O(N^3)$인 Floyd-Warshall 알고리즘을 사용해도 된다.
• 이후, $K$부터 시작하여, 가능한 모든 경로를 탐색하자.
  • 시간복잡도: $O((N-1)!)$ -> $(10-1)! = 362\ 800$이므로 이것도 가능하다.
• 모든 경로를 탐색하며 거친 최단거리의 합 중 최솟값이 답이 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int N, K;
    static int[][] T;

    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;
    static int sum;

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        N = Integer.parseInt(tk.nextToken());
        K = Integer.parseInt(tk.nextToken());

        T = new int[N][N];
        for (int i=0; i<N; i++) {
            tk = new StringTokenizer(rd.readLine());
            for (int j=0; j<N; j++) {
                T[i][j] = Integer.parseInt(tk.nextToken());
            }
        }
        visited = new boolean[N];

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

        // 이제부터 T는 경유 상관 없는 최단시간
        sum = 0;
        dfs(K, 0);
        System.out.println(ans);
    }

    static void dfs(int v, int depth) {
        if (depth == N-1) {
            ans = Math.min(ans, sum);
            return;
        }

        visited[v] = true;
        for (int i=0; i<N; i++) {
            if (visited[i]) continue;
            sum += T[v][i];
            dfs(i, depth + 1);
            sum -= T[v][i];
        }
        visited[v] = false;
    }
}

메모리 및 시간

• 메모리: 14660 KB
• 시간: 156 ms

리뷰

• $N \le 10$이라는 조건 때문에 너무나 널널하게 풀린 문제
• 알고리즘 분류의 '비트마스킹'은 DFS 대신 BFS를 사용한다면 사용할 것 같다.
• 체감 난이도에 비해 Floyd-Warshall 탓에 solved.ac 레이팅이 높게 책정된 문제