백준 5818 - SPUNJI

문제

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

리뷰

크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.

주어진 문제에서 스파이는 정보를 직접 파견을 나가 얻거나, 다른 스파이를 통해
전달받을 수 있고, 모든 스파이가 파악한 정보를 공유할 수 있는 상태로 만드는 것이
조건이다. 단, 파견을 나가 정보를 얻는 경우와 스파이끼리 만나 정보를 공유하는 경우
모두 비용이 소요된다. 따라서 비용을 최소화로 하며 모든 스파이끼리 정보를 공유할 수
있게 만드는 것이 중요하다.

따라서 최소 비용으로 모든 스파이간 정보가 공유될 수 있도록 하기 위해 크루스칼을
이용하였다. 스파이간 간선 정보(정보를 공유하는데 드는 비용)는 그저 비용 기준
최소힙에 바로 저장하였으며, 1~N의 스파이가 파견되어 정보를 파악하는 비용도
함께 고려하기 위해 해당 경우를 0과의 간선으로 간주하여 힙에 같이 저장하였다.
이후, MST를 형성하며 채택되는 간선들의 비용합을 통해 답을 도출했다.

로직의 시간복잡도는 간선의 개수가 $M=N\times(N-1)+N=N^2$일 때 크루스칼의
$O(NlogM)$으로 수렴하므로 $N=1,000$인 최악의 경우에도 무난히 제한 조건
5초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = parseInt(br.readLine());
        parent = new int[N + 1];

        StringTokenizer st;
        int w;
        for (int u = 1; u <= N; u++) {
            st = new StringTokenizer(br.readLine());
            for (int v = 1; v <= N; v++) {
                w = parseInt(st.nextToken());

                if (u == v) continue;

                pq.offer(new Edge(u, v, w));
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int u = 1; u <= N; u++) {
            w = parseInt(st.nextToken());
            pq.offer(new Edge(0, u, w));
        }

        System.out.println(kruskal(N + 1));
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return false;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }

        return true;
    }

    static long kruskal(int N) {
        Arrays.fill(parent, -1);
        int selected = 0;
        long sum = 0;

        while (!pq.isEmpty() && selected < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) continue;

            selected++;
            sum += e.w;
        }

        return sum;
    }

    static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과