[Gold III] 우주 탐사선 - 17182
성능 요약
메모리: 11784 KB, 시간: 108 ms
분류
백트래킹(backtracking), 비트마스킹(bitmask), 플로이드–와샬(floyd_warshall), 그래프 이론(graphs)
문제 설명
우주 탐사선 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)
출력
모든 행성을 탐사하기 위한 최소 시간을 출력한다.
풀이
처음에는 2차원 배열의 각 값들을 visit로 두고, dfs를 통해 최소값을 찾으려고 하였다.
노드에 대한 탐사 여부 조사는 비트마스킹으로 하고, 중복 방문이 가능하기 때문에 visit를 true로 바꾼 후 dfs가 끝난 후에 다시 false로 바꾸는 식으로 구현하였다.
이렇게 하니까 시간초과가 났다.
플로이드 와샬 알고리즘을 사용해서 미리 모든 행성 사이의 거리를 최소값으로 업데이트한 후에, dfs를 진행하면 더 빠른 시간으로 풀 수 있는 문제였다.
N이 최대 10이고, 이미 방문한 행성도 중복해서 갈 수 있다는 점이 플로이드 와샬 알고리즘을 사용할 수 있는 힌트인 것 같다.
package BOJ.Gold.g3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_17182_우주탐사선 {
static int N;
static int start;
static int[][] map;
static int ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
start = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
ans = Integer.MAX_VALUE;
// 플로이드 와샬
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
dfs(start, 0, 1 << start);
System.out.println(ans);
}
static void dfs(int idx, int time, int visit) {
if (visit == ((1 << N) - 1)) {
ans = Math.min(ans, time);
return;
}
for (int i = 0; i < N; i++)
if (i != idx && (visit & (1 << i)) == 0)
dfs(i, time + map[idx][i], (visit | (1 << i)));
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1744 - 수 묶기 (자바 Java) (0) | 2023.01.26 |
---|---|
[백준] 2193 - 이친수 (자바 Java) (0) | 2023.01.21 |
[백준] 15591 - MooTube (Silver) (자바 Java) (0) | 2023.01.11 |
[백준] 5052 - 전화번호 목록 (0) | 2023.01.09 |
[백준] 2533 - 사회망 서비스(SNS) (자바 Java) (0) | 2023.01.07 |