[백준 17182] 우주 탐사선 - JAVA //le_effort

우주 탐사선

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	841	418	322	50.949%

문제

우주 탐사선 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)

출력

모든 행성을 탐사하기 위한 최소 시간을 출력한다.

예제 입력 1 복사

xxxxxxxxxx
3 0
0 30 1
1 0 29
28 1 0

예제 출력 1 복사

xxxxxxxxxx
2

예제 입력 2 복사

xxxxxxxxxx
4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0

예제 출력 2 복사

xxxxxxxxxx
74

 

 

풀이

 

N값이 작으니 플로이드 와샬 알고리즘을 통해 각 정점간 거리를 파악해줍니다.

 

그 다음 dfs를 돌리면서 최단거리를 찾아내주면 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class Main {
    static int n,k;
    static int dist[][];
    static boolean visited[];
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws  IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        k = Integer.parseInt(t[1]);
        dist = new int[n][n];
        visited = new boolean[n];
        for(int i=0; i<n; i++) {
            t = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                dist[i][j] = Integer.parseInt(t[j]);
//              if(dist[i][j]==0) {
//                  dist[i][j] = 987654321;
//              }
            }
        }
        
        
        
        
        for(int k=0; k<n; k++) {
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(i==j) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
        visited[k] = true;
        dfs(0,k,0);
    System.out.println(ans);
        
    }
    public static void dfs(int level , int start, int sum) {
        if(level == n-1) {
            ans = Math.min(ans, sum);
            return ;
        }
        
        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(level+1,i,sum+dist[start][i]);
                visited[i] = false;
            }
        }
    }
}
​