백준 17182번: 우주 탐사선 (Java)

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

17182번: 우주 탐사선

문제

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

출력

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

 

---

 

풀이

모든 점을 방문하는데, N <= 10인 걸로 미루어보아 모든 점을 순서대로 방문하는 모든 경우의 수 (N-1!개)를 따져봐도 된다. 다만, 방문한 점을 중복하여 방문할 수 있기에, '모든 점에서 최단거리'를 구하고 경우의 수를 따져야 한다 -> 플로이드

 

배운 점

다만, '플로이드 후 최단 경로를 찾으면 중복해서 방문하는 경우때문에 비효율적이지 않을까?'하는 생각이 들었다. 가령, A->B로 가는 경로가 있을 때, C, D를 들른다면 A->B->C->D와 같은 경로는 비효율적이지 않나?

-> N-1!가지의 경우를 따지면서 알아서 A->C->D->B인 경로를 찾는다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[][] dist;
    static int N, K, ans = Integer.MAX_VALUE;
    static boolean[] visited;
    
    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());
        K = Integer.parseInt(st.nextToken());
        dist = new int[N][N];
        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());
            }
        }
        
        for (int k = 0; k < N; k++) {
            for (int j = 0; j < N; j++) {
                for (int i = 0; i < N; i++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        visited = new boolean[N];
        visited[K] = true;
        perm(1, K, 0);
        System.out.println(ans);
    }
 
    static void perm(int cnt, int prev, int d) {
        if (cnt == N) {
            ans = Math.min(ans, d);
        }
        
        for (int i = 0; i < N; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            perm(cnt+1, i, d + dist[prev][i]);
            visited[i] = false;
        }
    }
}