[BOJ] 백준 17182 : 우주 탐사선 (java)

🧪 17182 우주 탐사선

---

난이도 : 🌟 골드 3
유형 : 플로이드-워셜

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

 

📝 문제

---

우주 탐사선 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)

 

출력

 

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

 

🧐 핵심 로직 

---

1. fillGraph() 메서드는 입력 파일(input.txt)로부터 그래프의 가중치를 읽어와 2차원 배열 times에 저장한다. 이 배열은 노드 간의 이동 비용을 나타낸다.

 

2. floydWarshall() 메서드는 플로이드-워셜 알고리즘을 사용하여 그래프에서 모든 쌍 간 최단 경로를 계산한다. 이는 동적 계획법을 활용하여 현재 경로와 경유 노드를 비교해 최단 경로를 갱신한다.

 

3. dfs() 메서드는 깊이 우선 탐색(DFS)을 활용하여 가능한 모든 방문 순서를 탐색한다.

    3 - 1) depth는 현재 탐색 깊이를 나타내며, 방문한 노드의 개수를 추적한다.

    3 - 2) start는 현재 노드를 나타내며, 탐색의 진행 상황을 갱신한다.

    3 - 3) totalTime은 현재까지의 경로 비용을 누적한다.

    3 - 4) 모든 노드를 방문했을 경우(depth == n - 1), 현재까지의 총 비용(totalTime)과 결과값(res)을 비교하여 최소값을 갱신한다.

 

4. visited 배열은 이미 방문한 노드를 표시하여 중복 방문을 방지한다.

 

💻 최종 코드 (128 ms)

---

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

public class Main {

    static BufferedReader br;
    static int n, k, res;
    static int[][] times;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        res = Integer.MAX_VALUE;

        fillGraph();
        floydWarshall();

        visited = new boolean[n];
        visited[k] = true;
        dfs(0, k, 0);

        System.out.println(res);

        br.close();
    }

    private static void fillGraph() throws Exception {

        times = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                times[i][j] = Integer.parseInt(st1.nextToken());
            }
        }
    }

    private static void floydWarshall() {

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == j) continue;
                    times[i][j] = Math.min(times[i][j], times[i][k] + times[k][j]);
                }
            }
        }
    }

    private static void dfs(int depth, int start, int totalTime) {

        if (depth == n - 1) {
            res = Math.min(res, totalTime);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(depth + 1, i, totalTime + times[start][i]);
                visited[i] = false;
            }
        }
    }
}