백준 17182 - 우주 탐사선

문제

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

리뷰

처음에 이 문제를 접했을 때 플로이드-워셜과 다익스트라 두 가지 관점으로 접근을 하려 했었다.
하지만 모든 정점을 방문하는 경로에서 시작점외 다른 정점에서 여타 정점까지 도달하는
최소 비용도 도출해야 했기에 결론적으로 플로이드-워셜을 사용해야 했다.

또한, 모든 정점을 방문해야 한다는 문제조건을 구현함에 있어 모든 정점을 방문하는 경로의
경우의 수를 구해야 했고 이를 실현하는데 dfs 를 활용했다.

플로이드-워셜은 전형적이고, dfs만 다음과 같이 구성하였다.

• 파라미터로 현재 정점(current), 현재 누적 거리(dist), 방문 행성 수(planet)을 설정
• 누적 거리가 기존에 도출한 답안(ans, 초기값 MAX_VALUE)보다 크면 진행 중단
• 모든 행성을 방문하였으면 ans 를 dist와 비교해 더 작은 값으로 갱신
• 이외의 경우 탐색을 진행, 모든 경우의 수를 구해야 하기에 탐색 진행 후 visited=false 처리

문제 조건에서 N이 최대 10이므로 플로이드 워셜의 최대 연산은 $1000$($O(N^3)$)이고
dfs 의 최대 연산은 $100$($O(N^2)$)이다. 시간 제한 조건인 1초를 무던히 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;
import static java.lang.Integer.MAX_VALUE;


public class Main {

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

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        int N = parseInt(st.nextToken());
        int K = parseInt(st.nextToken());
        map = new int[N][N];
        visited = new boolean[N];

        for (int i = 0; i < map.length; i++)
            Arrays.fill(map[i], MAX_VALUE);


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

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

        System.out.println(ans);
        in.close();
    }

    static void dfs(int current, int dist, int planet) { // O(N^2)
        if (dist > ans) return;

        if (planet == visited.length) {
            ans = Math.min(ans, dist);
            return;
        }

        for (int i = 0; i < visited.length; i++) {
            if (i == current) continue;

            if (!visited[i]) {
                visited[i] = true;
                dfs(i, dist + map[current][i], planet + 1);
                visited[i] = false;
            }
        }
    }


    static void floyd() { // O(N^3)
        for (int k = 0; k < map.length; k++)
            for (int i = 0; i < map.length; i++)
                for (int j = 0; j < map.length; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE)
                        continue;

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }

    }
}

결과