[백준 17182] 우주 탐사선

접근방법

이 문제는 입력으로 행성의 위치가 변하기 때문에 플로이드 워셜 알고리즘으로 모든 시작노드에서 모든 목적지 노드까지의 최단 거리를 구해준다.

이후, 모든 행성을 탐사하기 위해 드는 최소 비용을 구하기 위해서는 시작노드를 DFS의 매개변수로 전달해주고 모든 노드를 탐색할 수 있는 경로를 탐색하면서 최소 비용을 찾는다.

 

방문하는 순서에 따라서 최단경로가 다르기 때문에 모든 경로를 탐색한 뒤 minCost를 갱신해주어야 한다.

• 2 -> 0 -> 1 : 101
• 2 -> 1 -> 0 : 2

이때의 dfs의 시간복잡도는 처음에 10개의 노드 탐색 -> 9개의 노드 탐색 -> 8개의 노드 탐색 .... 이므로 O(N!) 이다.

 

어려웠던 부분

1. DFS 알고리즘 작성하는 부분

public static void dfsFail(int start, int cost) {
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfsFail(i, cost + map[start][i]);
            visited[i] = false;
        }
    }

    minCost = Math.min(minCost, cost);
}

• dfs 로직을 위 메서드처럼 작성했는데 이때, 모든 노드를 탐색하지 않았는데도 minCost를 갱신하게 되어 잘못된 값을 얻게 된다.
  
  예를 들어, visited가 [T, T, T] 인 경우에 minCost를 갱신한 뒤 visited[2]를 false로 되돌리고 for 문이 종료된다.
  이때, dfsFail()의 매개변수로 전달받은 cost는 2개의 노드를 탐색한 비용이기 때문에 minCost가 2개의 노드를 탐색한 비용으로 갱신된다.

구현

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

public class Solution_for_17182 {
    static int N;   // 행성의 개수
    static int K;   // ana호가 발사되는 행성의 위치

    static int[][] map;
    static boolean[] visited;

    static int minCost = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        for (int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        floyd();

        visited = new boolean[N];
        visited[K] = true;
        dfs(K, 0, 1);

        System.out.println(minCost);
    }

    public static void floyd() {
        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
    }

    public static void dfs(int start, int cost, int cnt) {

        if (cnt == N) {
            minCost = Math.min(minCost, cost);
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i, cost + map[start][i], cnt+1);
                visited[i] = false;
            }
        }
    }
}