[BOJ17182] 우주 탐사선 (플로이드 워셜, 완전탐색)알고리즘/최단 경로2023. 9. 4. 17:19
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/17182
문제 풀이
플로이드 워셜로 각 노드별 다른 노드에 대한 최단 경로를 구할 수 있었다. 그런데 출발 행성 K 위치가 주어졌을 때 다른 행성을 탐색하는데 걸리는 시간을 어떻게 구할 지에서 삽질을 여러번 하였다. 결국 재귀 함수 사용한 완전 탐색으로 구하면 방문 여부 체크하며 구하면 되는 문제였다. "이미 방문한 행성도 중복해서 갈 수 있다"는 문제 지문이 함정이 아니었나 싶다
스스로 완전 탐색에 대한 생각을 해놓고 왜 다른 기술 블로그를 찾은 건지 .. 배운 지식을 소화하자 ..
- N : 행성의 개수 (노드의 수)
- 플로이드 워셜 시간 복잡도 : O(N^3)
- 시작 행성 위치 K에서 다른 모든 행성을 탐색하는데 걸리는 시간의 경우 완전 탐색으로 O(N!) = (10!) = 약 362만
매 턴마다 방문 가능한 행성의 수가 10 * 9 * 8 * 7 * ... 로 줄어드는 형태
- 총 시간 복잡도 : 플로이드 워셜 + 시작 행성 K에서 시작하는 완전 탐색 = O(1000 + 362만)
- 1초에 1억번 연산 가정시 충분히 가능
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static int N, K;
static int[][] floyd;
static int RESULT;
static boolean[] visit;
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 행성의 개수 (노드 수, 최대 10개)
K = Integer.parseInt(st.nextToken()); // 출발 행성 위치
floyd = new int[N][N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
floyd[i][j] = Integer.parseInt(st.nextToken());
}
}
visit = new boolean[N];
RESULT = Integer.MAX_VALUE;
}
static void pro() {
for(int k = 0; k < N; k++) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
}
}
}
dfs(K, 0, 0); // K 행성 출발, depth, 탐사하는데 걸리는 총 시간 (초기 0)
System.out.println(RESULT); // 결과 출력
}
static void dfs(int node, int depth, int total) {
if(depth == N) {
RESULT = Math.min(RESULT, total);
return;
}
for(int i = 0; i < N; i++) {
if(visit[i]) continue;
visit[i] = true;
dfs(i, depth + 1, total + floyd[node][i]); // node -> i 로 가는 최소 비용
visit[i] = false;
}
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
반응형
'알고리즘 > 최단 경로' 카테고리의 다른 글
[BOJ11780] 플로이드2 (플로이드 워셜, 최단경로) (0) | 2023.09.04 |
---|---|
[BOJ13424] 비밀 모임 (플로이드 워셜, 최단 경로) (0) | 2023.09.04 |
[BOJ1613] 역사 (플로이드 워셜) (1) | 2023.09.03 |
[BOJ1507] 궁금한 민호 (플로이드 워셜) (1) | 2023.09.03 |
[BOJ2660] 회장뽑기 (플로이드 워셜, 최단거리) (0) | 2023.09.02 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!