[java][백준] 17182 - 우주탐사선

문제

풀이

문제해석

1. 우주선 ana호가 모든 행성을 탐사하는 최소시간을 계산하려고 한다.

2. ana호는 자기 자신을 제외한 모든 행성으로 떠날 수 있다. 이것이 2차원 행렬로 주어진다.

3. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라

문제 풀이

1. 행성의 개수가 많지 않아서 플로이드-워셜 알고리즘을 사용해도 괜찮다.

2. 2차원 행렬이 주어지고 이를 가지고 플로이드-워셜 알고리즘을 적용하면 각 행성으로 가는 최소 시간을 구할 수 있다.

3. 그 후 dfs를 통해 완전탐색을 해서 최소시간을 구한다.

소스코드

package online.judge.baekjoon;

import java.util.Scanner;

/**
 * 우주 탐사선
 * 골드 3
 */
public class No17182 {
    static boolean[] visited;
    static int n;
    static int answer = Integer.MAX_VALUE;
    static int[][] graph;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        n = scan.nextInt();
        int k = scan.nextInt();

        graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = scan.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {   //거쳐오기
            for (int j = 0; j < n; j++) {   //출발
                for (int l = 0; l < n; l++) {   //도착
                    if (j == l) continue;
                    //j에서 l로 가는 것 보다 j에서 i 또 i에서 l로 가는게 더 빠를경우
                    if (graph[j][l] > graph[j][i] + graph[i][l]) {
                        graph[j][l] = graph[j][i] + graph[i][l];
                    }
                }
            }
        }

        visited = new boolean[n];
        visited[k] = true;

        dfs(k, 0, 0);

        System.out.println(answer);

    }

    private static void dfs(int k, int sum, int depth) {
        if(depth == n-1){
            answer = Math.min(answer, sum);
            return;
        }
        for (int i = 0; i < n; i++) {
            if(visited[i] || i == k) continue;
            visited[i] = true;
            dfs(i, sum + graph[k][i], depth+1);
            visited[i] = false;
        }
    }

}

 

마무리

1. 최단 경로 알고리즘에 대해 학습했다. (다익스트라, 벨만포드, 플로이드-워셜)

2. 플로이드-워셜은 비교적 꼭짓점이 적고 중복적으로 겹치는 부분이 있을 때 사용하면 좋을 것 같았다.

3. 아무래도 쉽지 않은 알고리즘이다 보니 반복숙달이 중요할 것으로 보인다.