[백준] 우주 탐사선 17182번 (java) 플로이드 워샬, 순열

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

 

풀이 방법

순열 문제라는 것을 알 수 있다.

n이 10까지 밖에 되지 않으므로 방문할 순서를 정하고 최소를 구하면 된다.

단순히 순열만 사용해서 구해도 되지만 플로이드 워샬을 사용해 보고 싶어서 사용해 보았다.

import java.io.*;
import java.nio.Buffer;
import java.util.*;


public class Main {

    static int n,k, ans;
    static int[][] dist;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        ans = Integer.MAX_VALUE;
        dist = new int[n][n];
        visited = new boolean[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 i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                for (int z = 0;z < n;z++) {
                    dist[i][j] = Math.min(dist[i][z] + dist[z][j], dist[i][j]);
                }
            }
        }

        // 순열 하기
        visited[k] = true;
        dfs(k, 1, 0);
        System.out.println(ans);
    }

    public static void dfs(int cur, int cnt, int cost) {
        if (cnt == n) {
            ans = Math.min(ans, cost);
            return ;
        }
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            dfs(i, cnt + 1, cost + dist[cur][i]);
            visited[i] = false;
        }
    }
}