[자바/플로이드워셜] 백준 17182. 우주탐사선

문제

백준 17182. 우주탐사선

해석

"중복으로 노드를 방문 가능하다"는 점에서 최소신장트리를 구하는 알고리즘보단 플로이드워셜을 사용하는 게 적절하겠단 판단을 했다.

 

그렇게 각 노드 간 weight 계산을 마치고 나서는, N이 10까지이므로 완전탐색을 이용하여 최소 비용 합을 계산하면 되겠다고 판단했다.

 

 결론 : 플로이드워셜 + 순열(next permutation)을 이용하여 완탐을 돌아서 최소 비용을 계산했다.

--

더 배우고자 다른 이의 코드를 보고 뜯어봤는데, 다른 이는 DFS를 이용하여 최소 비용 합을 계산하였다. 눈에 띄는 차이는 플로이드 워셜을 사용할 때 방문 노드를 체크하지 않았던 점이다. 나의 경우에는 플로이드 워셜을 하면서 각 노드 간 weight를 계산할 때 애초에 다른 노드를 방문하는 로직이 포함되니, 나중에 완탐할 때 이 정보도 활용하자는 생각에 이를 저장하기 위해 Pair라는 클래스를 선언하여 활용하고자 했었다. 결론적으로는 상대 로직(112ms) 대비 내 로직(188ms)이 더 수행시간이 느렸다. 어차피 완탐을 하게 되면 모든 경우를 탐색하게 되니 중복되는 경우를 감안하여 최적의 코스를 어차피 탐색하게 될 것이며, 내 로직의 경우 그런 중복 케이스를 제거하겠단 마음에 객체 생성이나 객체 접근을 수행했던 게 오히려 전체 경우 탐색하는 시간보다 무거웠던 것으로 보인다. 다시금 자바에서 객체 생성 및 접근이 비싼 연산임을 깨닫게 된다.

코드

플로이드워셜 + next permutation

public class Main {
    /*
    * 티어 : 골드3
    *
    * 수행 시간 : 188 ms
    *
    * 메모리 : 15912 KB
    *
    * 시간복잡도 : O(N^3 + N!); 플로이드와셜 + 넥퍼
    * */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] adj = new int[n][n];

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

        int ans = solution(n, k, adj);

        bw.write(String.valueOf(ans));

        br.close();
        bw.flush();
        bw.close();
    }

    static int K;
    static int N;
    static Pair[][] dist;
    static int ans;
    private static int solution(int n, int start, int[][] arr) {
        // k는 0부터 시작
        // dist도 0번 인덱스 ~ n-1번 인덱스로 구성

        dist = new Pair[n][n];
        K = start;
        N = n;

        int[] nodes = new int[n - 1];
        // nodes 정보 init
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (i == start) { // 시작 노드 제외하고
                continue;
            }
            nodes[idx++] = i; // 나머지 노드들 저장
        }

        // init dist
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = new Pair(arr[i][j], 1 << j);
            }
        }

        // floyd
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int joinWeight = dist[i][k].weight + dist[k][j].weight;
                    if (dist[i][j].weight >= joinWeight) {
                        dist[i][j] = new Pair(joinWeight, dist[i][k].visit | dist[k][j].visit); // 방문한 노드 정보까지 같이 저장
                    }
                }
            }
        }

        ans = (int) 1e9; // 적절히 큰 값으로 초기화

        getAns(nodes); // 정렬 순열에서 정답 1회 계산

        // 넥퍼 수행하여 ans 업데이트
        while (true) {
            if (!np(nodes)) {
                break;
            }
        }

        return ans;
    }

    private static boolean np(int[] nodes) {
        final int LAST_IDX = nodes.length - 1;

        int i = LAST_IDX;
        while (i > 0 && nodes[i - 1] >= nodes[i]) {
            --i;
        }

        if (i == 0) {
            return false;
        }

        int j = LAST_IDX;
        while (nodes[i - 1] >= nodes[j]) {
            --j;
        }

        swap(nodes, i - 1, j);

        int k = LAST_IDX;
        while (i < k) {
            swap(nodes, i++, k--);
        }

        // 순열 완성 시점
        getAns(nodes); // 정답 계산

        return true;
    }

    private static void getAns(int[] nodes) {
        int visited = (1 << K); // 시작 노드 방문하고 시작
        int fin = (1 << N) - 1; // 모든 노드 방문
        int res = 0; // 이동 weight 합
        int prev = K;
        for (int node : nodes) { // 이동 경로를 나타냄
            if ((visited & fin) == fin) { // 이미 모든 노드 탐색했으면 종료
                break;
            }
            if ((visited & 1 << node) != 0) { // 어찌저찌 이미 방문한 노드면 pass
                continue;
            }
            res += dist[prev][node].weight;
            visited |=  dist[prev][node].visit;
            prev = node;
        }
        ans = Math.min(ans, res);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static class Pair {
        int weight, visit;

        private Pair(int w, int v) {
            weight = w;
            visit = v;
        }
    }
}

 

다른이의 풀이 : 플로이드워셜 + DFS

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

public class Main {
    /**
    * 시간복잡도 : O(N^3 + N^2) // 플로이드워셜 + DFS
    *
    * 수행시간 : 112 ms
    */
    static int N,start;
    static int[][] board;
    static int answer=Integer.MAX_VALUE;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {

        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        st= new StringTokenizer(bf.readLine());

        N=Integer.parseInt(st.nextToken());
        start=Integer.parseInt(st.nextToken());

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


        // floyd warshall
        for(int k=0;k<N;k++)
        {
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<N;j++)
                {
                    if(i==j) continue;

                    board[i][j]=Math.min(board[i][j],board[i][k]+board[k][j]);
                }
            }
        }

        // dfs
        visited=new boolean[N];
        visited[start]=true;
        dfs(start,0,0,visited);
        System.out.println(answer);

    }
    public static void dfs(int node, int sum,int depth,boolean[] v)

    {

        if(depth==N-1)
        {
            answer=Math.min(answer,sum) ;
            return;
        }

        for(int i=0;i<N;i++)
        {
            if(!visited[i])
            {
                visited[i]=true;
                dfs(i,sum+board[node][i],depth+1,v);
                visited[i]=false;
            }
        }


    }
    public static boolean allVisit(boolean[] v)
    {
        boolean flag=true;

        for(int i=0;i<N;i++)
        {
            if(!v[i])
                flag=false;
        }

        return flag;

    }
}