[BOJ17182] 우주 탐사선 (플로이드 워셜, 완전탐색)

 

 

---

문제 링크 

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

17182번: 우주 탐사선

 

문제 풀이 

플로이드 워셜로 각 노드별 다른 노드에 대한 최단 경로를 구할 수 있었다. 그런데 출발 행성 K 위치가 주어졌을 때 다른 행성을 탐색하는데 걸리는 시간을 어떻게 구할 지에서 삽질을 여러번 하였다. 결국 재귀 함수 사용한 완전 탐색으로 구하면 방문 여부 체크하며 구하면 되는 문제였다. "이미 방문한 행성도 중복해서 갈 수 있다"는 문제 지문이 함정이 아니었나 싶다

 

스스로 완전 탐색에 대한 생각을 해놓고 왜 다른 기술 블로그를 찾은 건지 .. 배운 지식을 소화하자 ..

 

- N : 행성의 개수 (노드의 수)

- 플로이드 워셜 시간 복잡도 : O(N^3) 

- 시작 행성 위치 K에서 다른 모든 행성을 탐색하는데 걸리는 시간의 경우 완전 탐색으로 O(N!) = (10!) = 약 362만

 

매 턴마다 방문 가능한 행성의 수가 10 * 9 * 8 * 7 * ... 로 줄어드는 형태 

 

- 총 시간 복잡도 : 플로이드 워셜 + 시작 행성 K에서 시작하는 완전 탐색 = O(1000 + 362만) 

- 1초에 1억번 연산 가정시 충분히 가능

 

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    static int N, K;

    static int[][] floyd;

    static int RESULT;

    static boolean[] visit;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 행성의 개수 (노드 수, 최대 10개)
        K = Integer.parseInt(st.nextToken()); // 출발 행성 위치

        floyd = new int[N][N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                floyd[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visit = new boolean[N];
        RESULT = Integer.MAX_VALUE;
    }

    static void pro() {
        for(int k = 0; k < N; k++) {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }

        dfs(K, 0, 0); // K 행성 출발, depth, 탐사하는데 걸리는 총 시간 (초기 0)

        System.out.println(RESULT); // 결과 출력
    }

    static void dfs(int node, int depth, int total) {
        if(depth == N) {
            RESULT = Math.min(RESULT, total);
            return;
        }

        for(int i = 0; i < N; i++) {
            if(visit[i]) continue;
            visit[i] = true;

            dfs(i, depth + 1, total + floyd[node][i]); // node -> i 로 가는 최소 비용

            visit[i] = false;
        }
    }


    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
    
}