BOJ 17182 우주 탐사선

https://www.acmicpc.net/problem/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 줄에 걸쳐 각 행성 간 이동 시간 $T_{ij}$ 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ $T_{ij}$ ≤ 1000)

---

출력

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

---

예제 입력 1

3 0
0 30 1
1 0 29
28 1 0

예제 출력 1

2

예제 입력 2

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

예제 출력 2

74

---

코드

최단 경로 알고리즘 중 하나인 플로이드 워셜을 알고는 있었지만, 실제로 문제로 풀어본 적은 한 번도 없었다.

플로이드 워셜은 시간 복잡도가 $O(N^3)$이기 때문에, 웬만하면 문제의 풀이로 적용하기 힘들다는 고정관념이 있었다.

그래서 처음 이 문제를 봤을 때, 어떻게 풀어야 할 지 전혀 감이 잡히지 않았다.

그렇게 고민하다가 문제를 자세히 읽어보며 플로이드 워셜 알고리즘을 적용하는 문제일 거라고 생각한 이유는 행성의 개수 N이 최대 10개로 매우 적어 $O(N^3)$을 충분히 수행할 수 있다는 것이었다.

문제 풀이 과정은 다음과 같다.

1. 주어진 행성 간 이동 시간 T와 플로이드 워셜 알고리즘으로 행성 간 최소 이동 시간을 계산한다.
2. 출발 행성부터 시작해서 브루트포스로 모든 행성을 방문한 시간 중에서 최소 시간을 출력한다.

   행성의 방문 여부를 체크하기 위해서 비트마스킹을 사용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int K;
    static int minTime = Integer.MAX_VALUE;
    static int[][] explorationTime;
    static int[][] minExplorationTime;

    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());
        explorationTime = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                explorationTime[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        initializeMinExplorationTime();
        
        calculateMinTime(K, 1 << K, 0);
        
        System.out.println(minTime);
    }

    static void initializeMinExplorationTime() {
        minExplorationTime = explorationTime.clone();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    int stopByTime = explorationTime[j][i] + explorationTime[i][k];
                    minExplorationTime[j][k] = Integer.min(minExplorationTime[j][k], stopByTime);
                }
            }
        }
    }

    static void calculateMinTime(int planet, int visited, int time) {
        if(Integer.bitCount(visited) == N) {
            minTime = Integer.min(minTime, time);
            return;
        }

        for (int i = 0; i < N; i++) {
            if((visited & 1 << i) == 0) {
                calculateMinTime(i, visited | 1 << i, time + minExplorationTime[planet][i]);
            }
        }
    }
}