[백준 2463] 비용 (JAVA)

문제

---

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

풀이

---

Disjoint-Set 응용하여 해결할 수 있는 문제입니다.

가중치가 가장 큰 간선부터 하나씩 연결하면서 확인하며 이미 연결이 되어있는지 아닌지 확인합니다. 연결이 되어있지 않으면 연결 후 가중치를 계산하여 결과값에 더해줍니다.

먼저 간선을 내림차순으로 정렬합니다. 그리고 가중치의 총합을 구합니다. (totalWeight = 45)

x	y	w
3	6	15
1	2	10
2	6	6
3	4	5
3	5	4
4	5	3
2	3	2

1) 3-6를 연결합니다.

• 1은 2부터6까지 ... 5는 6으로 확인할 수 있습니다. (Cost(u,v)일때 u < v)
• 1개 연결되었으므로 45 * 1
• totalWeight -= 15

2) 1-2를 연결합니다.

• 연결된 부분이 1개이므로 30 * 1
• totalWeight -= 10

3) 2-6를 연결합니다.

• 연결된 부분이 4개이므로 20 * 4
• totalWeight -= 6

4) 3-4를 연결합니다.

• 연결된 부분이 4개이므로 14 * 4
• totalWeight -= 5

4) 3-5를 연결합니다.

• 연결된 부분이 5개이므로 9 * 5
• totalWeight -= 4

4) 4-5를 연결합니다.

• 연결된 부분이 0개이므로 5 * 0
• totalWeight -= 3

4) 2-3를 연결합니다.

• 연결된 부분이 0개이므로 2 * 0

총합은 256입니다.

몇개의 노드가 연결되었는지 확인하기 위해서는 childCount 배열을 통해 x와 y를 결합할 때 childCount[find(x)] * childCount[find(y)]를 하고 한쪽으로 값을 옮겨줍니다.

코드

---

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

public class Main {

    public static final int MOD = 1000000000;
    public static int N, M;
    public static int[] parents, childCount;

    public static void main(String[] args) throws IOException {

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        Edge[] edges = new Edge[M];
        long totalWeight = 0;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x, y, w;
            x = Integer.parseInt(st.nextToken()) - 1;
            y = Integer.parseInt(st.nextToken()) - 1;
            w = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(Math.min(x, y), Math.max(x, y), w);
            totalWeight += w;
        }
        Arrays.sort(edges);

        make();

        long ans = 0;
        for (Edge edge : edges) {
            ans += totalWeight * union(edge.start, edge.end);
            ans %= MOD;
            totalWeight -= edge.weight;
        }

        System.out.println(ans);
        br.close();
    }

    public static int find(int num) {
        if (parents[num] == num) return num;
        return parents[num] = find(parents[num]);
    }

    public static long union(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);
        if (aParent == bParent) return 0;

        parents[bParent] = aParent;
        long result = (long) childCount[aParent] * childCount[bParent];
        childCount[aParent] += childCount[bParent];
        childCount[bParent] = 0;
        return result;
    }

    public static void make() {
        parents = new int[N];
        childCount = new int[N];
        for (int i = 0; i < N; i++) {
            parents[i] = i;
            childCount[i] = 1;
        }
    }

    public static class Edge implements Comparable<Edge> {
        int start, end, weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return o.weight - this.weight;
        }
    }
}