[BOJ/Floyd-Warshall + DFS] 백준 17182 - 우주 탐사선 (Java)

백준 17182 - 우주 탐사선

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

문제

행성의 위치 0부터 시작해 0은 행렬에서 0번째 인덱스에 해당하는 행성
2차원 행렬에서 i, j번 요소는 i번째 행성에서 j번째 행성에 도달하는데 걸리는 시간
i와 j가 같을 때는 항상 0이 주어짐
탐사 후 다시 시작 행성으로 돌아올 필요 X 이미 방문한 행성도 중복해서 갈 수 있음

입력
첫째 줄: 행성의 개수 N, ana호가 발사되는 행성 위치 K (2 <= N <= 10, 0 <= K < N)
다음 N줄: 각 행성 간 이동 시간 $T_{ij}$ (0 <= $T_{ij}$ <= 1000)
출력: 모든 행성을 탐사하기 위한 최소 시간

---

풀이

Floyd–Warshall

어떤 행성에서 다른 행성으로 가는 데 걸리는 최소 시간 미리 계산

-> 중간 경유지(`k`) 지날 때 더 빠르면 그 값으로 갱신 

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

 

DFS + Back-Tracking

시작 행성 K에서 출발해 N개의 행성 모두 방문하는 최소 비용 찾기

static void dfs(int start, int cnt, int cost) {
    if (cnt == N) {
        ans = Math.min(ans, cost);
        return;
    }

    for (int next = 0; next < N; next++) {
        if (!visited[next]) {
            visited[next] = true;
            dfs(next, cnt + 1, cost + dist[start][next]);
            visited[next] = false;
        }
    }
}

---

코드

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

// 우주 탐사선
public class boj_17182 {
    static int N, K;
    static int[][] dist;
    static boolean[] visited;
    static int ans = Integer.MAX_VALUE;

    static void dfs(int start, int cnt, int cost) {
        if (cnt == N) {
            ans = Math.min(ans, cost);
            return;
        }

        for (int next = 0; next < N; next++) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next, cnt + 1, cost + dist[start][next]);
                visited[next] = false;
            }
        }
    }

    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());

        dist = 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++) {
                dist[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++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

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

        System.out.println(ans);
    }
}