백준 27498 - 연애 혁명

문제

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

풀이

크루스칼 알고리즘을 응용하여 간단히 풀이할 수 있는 문제였다.
로직은 다음 과정을 거쳐 전개된다.

1. 간선(관계) 정보를 입력받으며 애정도 기준 최대힙에 저장한다. 이 때 이미 이뤄진 관계의 경우 제거 대상에서 제외해야 하므로 유니온 연산을 적용해준다. 동시에 채택한 간선 개수를 증가시킨다.
2. 최대힙에서 크루스칼 알고리즘을 활용해 채택한 간선 수가 $N-1$에 도달할 때까지 (모든 정점이 최소의 간선으로 연결될 때까지) 간선을 채택한다. 제거되는 간선의 애정도 합을 구해야 하기 떄문에 진행 과정에서 채택되지 않은 간선의 애정도를 합해준다.
3. 간선 채택 후 힙에 남아있는 간선 역시 제거되는 경우이므로 그 애정도를 합해준다. 힙을 애정도 기준 최대힙으로 정의했기 때문에 해당 값은 자연스레 포기하도록 만든 애정도의 합의 최솟값이 된다.

로직의 시간복잡도는 크루스칼을 사용하는 부분의 $O(MlogM)$으로 수렴하고 이는
$M=100,000$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static int[] parent;

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

        parent = new int[N + 1];
        Arrays.fill(parent, -1);

        int count = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> Integer.compare(e2.w, e1.w));
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());
            boolean success = parseInt(st.nextToken()) == 1;

            if (success) {
                union(u, v);
                count++;
                continue;
            }

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

        int sum = 0;

        while (count < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) {
                sum += e.w;
                continue;
            }

            count++;
        }

        sum += pq.stream().mapToInt(e -> e.w).sum();
        System.out.println(sum);
        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 p1 = find(u);
        int p2 = find(v);

        if (p1 == p2) return false;

        if (parent[p1] < parent[p2]) {
            parent[p2] += parent[p1];
            parent[p1] = p2;
        } else {
            parent[p1] += parent[p2];
            parent[p2] = p1;
        }

        return true;
    }

    static class Edge {
        int u, v, w;

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

결과