[백준 / BOJ] 17182 우주 탐사선 (완전탐색)

문제

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

17182번: 우주 탐사선

우주탐사선 ans호가 있다.

ans호는 N개의 행성을 모두 탐사하는데 걸리는 최소시간을 계산하려한다.

 

N개의 행성끼리 이동하는데 걸리는 시간이 주어질때 모든 행성을 탐사하기 위한 최소 시간을 출력하는 문제다.

 

---

풀이

플로이드 와샬로 최단경로를 만들어주고, 비트마스킹을 이용한 완전탐색으로 답을 찾은 문제다.

(거의 3달만의 플로이드 와샬이라 알고리즘조차 가물 가물했다..)

 

N이 최대 10이므로, 완전탐색을 수행해도, O((N-1)!) 시간복잡도가 나와 문제를 넉넉히 풀수있다.

 

로직

1. 플로이드 와샬로 모든 경로를 최단경로로 업데이트 해준다.

간단한 예를들어 설명하면, 행성이 5개있으며 각각 A,B,C,D,E 라는 이름을 갖고있다고 가정하자, A에서 E행성으로 가는경로는

A -> E

A -> B -> C -> E 

A -> C -> E

위와 같은 무수히 많은 경로중 무엇이 최소경로인지 알수없다. 따라서, 모든 경로를 봐주며 최단경로로 업데이트 해줘야한다. 이를 모든 노드에 대해 수행해줘야한다.

 

소스코드

    private void floyd(){
        for(int mid = 0; mid < N; mid++)
            for(int from = 0; from < N; from++)
                for(int to = 0; to < N; to++) arr[from][to] = Math.min(arr[from][mid] + arr[mid][to], arr[from][to]);
    }

 

2. K번째 노드에서 시작한 모든경로중 최소경로를 찾아준다.

(이 과정에서 중복방문을 없애주기 위해 비트마스킹을 사용했다.)

성공적으로 구현된 완전탐색에서 예외는 있을수없으니, 완전탐색으로 답을 어떻게 구할수있는지는 따로 설명하지 않겠다.

 

완전탐색을 쓰기위해 신경써야할 부분은 알고리즘 수행시간이다.

시간복잡도를 계산해보면,

 

1. 첫 번째 탐색에서 선택할수있는 경우의 수는 (자신을 제외한) N-1개이다.

 

2. 두 번째 탐색에서 선택할수있는 경우의 수는 N-2이다.

.

.

.

N. N 번째 탐색에서 선택할수있는 경우의 수는 1개이다.

 

따라서 총 반복횟수는 (N-1)!이 된다.

이때, N이 최대 10이므로 넉넉하다.

 

소스코드

    private int find(int K, int bit){
        if(bit == capBit) return 0;
        int ans = 987654321;
        for(int i = 0; i < N; i++){
            int nBit = bit | (1 << i);
            if(nBit == bit) continue; 
            ans = Math.min(ans, find(i, nBit)+arr[K][i]);
        }
        return ans;
    }

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/17182%20%EC%9A%B0%EC%A3%BC%20%ED%83%90%EC%82%AC%EC%84%A0/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃