[알고리즘] BOJ 17182 우주 탐사선 (JAVA)

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

 

 

백준 골드3으로 설정된 문제였다.

 

 

모든 행성 간의 소요 시간을 확인하기 위해 플로이드 워셜을 통해 시간을 구해두고,

 

 

백트래킹을 통해 모든 행성을 탐사하며 최단 거리를 갱신하는 방식으로 구현했다.

 

 

import java.io.*;

import java.util.*;

public class boj17182 {

    static int N, K, result;

    static int dist[][];

    static boolean isVisited[];

    public static void backTracking(int src, int sum, int depth) {

        if (depth == N - 1) {

            result = Integer.min(result, sum);

            return;

        }

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

            if (!isVisited[i]) {

                isVisited[i] = true;

                backTracking(i, sum + dist[src][i], depth + 1);

                isVisited[i] = false;

            }

        }

    }

    public static void FloydWrasahll() {

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

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

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

                    dist[i][j] = Integer.min(dist[i][j], dist[i][k] + dist[k][j]);

                }

            }

        }

    }

    public static void pre() 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());

        result = Integer.MAX_VALUE;

        dist = new int[N][N];

        isVisited = new boolean[N];

        isVisited[K] = true;

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

            }

        }

    }

    public static void main(String args[]) throws IOException {

        pre();

        FloydWrasahll();

        backTracking(K, 0, 0);

        System.out.println(result);

    }

}

 

 

해당 코드의 실행시간은 다음과 같다.