알고리즘/알문풀(백준, 프로그래머스, 코드트리)
[알고리즘] BOJ 17182 우주 탐사선 (JAVA)
ragabys
2024. 6. 2. 18:23
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);
}
}
해당 코드의 실행시간은 다음과 같다.
