[Java] 백준 17182번 : 우주 탐사선*

1. 문제

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

17182번: 우주 탐사선

 

 

2. 풀이 과정

최단 경로를 구하는데, 지나온 길을 다시 탐색할 수 있기 때문에 플로이드 워샬 알고리즘으로 각 노드마다 갈 수 있는 최단 거리를 구하고 DFS 탐색을 했다.

이때, DFS 탐색의 결과는 어떤 노드를 먼저 방문하냐

즉 방문하는 노드 순서에 따라 달라지므로 순열 탐색으로 볼 수 있다.

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

public class Main {

    static int N, map[][], result;
    
    public static void permutation(int start, int time, int visited){
        if(visited == (1<<N)-1){
            result = Math.min(result, time);
            return;
        }

        for(int i=0; i<N; i++){
            if((visited & (1<<i))!=0){
                continue;
            }
            permutation(i,time + map[start][i], visited | (1<<i));
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        map = new int[N][N];

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

        //Floyd Warshall
        for(int k=0; k<N; k++){
            for(int i=0; i<N; i++){
                if(i==k){continue;}
                for(int j=0; j<N; j++){
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }

        //순열 탐색
        result = 10001;
        permutation(K, 0, (1<<K));
        System.out.println(result);
    }
}

 

 

결과