[BOJ] 1922.네트워크 연결

문제 원본 : https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int[] parent;
    static int[] depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        StringTokenizer st = null;
        int a, b, c;
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            edges.add(new Edge(c, a, b));
        }

        parent = new int[n + 1];
        depth = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }

        Collections.sort(edges, (o1, o2) -> o1.cost - o2.cost);

        int ans = 0;
        for (int i = 0; i < m; ++i) {
            if (find(edges.get(i).a) == find(edges.get(i).b)) {
                continue;
            }

            union(edges.get(i).a, edges.get(i).b);
            ans += edges.get(i).cost;
        }

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

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

    public static class Edge {
        public int cost;
        public int a;
        public int b;

        public Edge(int cost, int a, int b) {
            this.cost = cost;
            this.a = a;
            this.b = b;
        }
    }

    public static int find(int u) {
        if (u == parent[u]) {
            return u;
        }

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

    public static void union(int u, int v) {
        u = find(u);
        v = find(v);

        if (u == v) {
            return;
        }

        if (depth[u] > depth[v]) {
            int tmp = u;
            u = v;
            v = tmp;
        }

        parent[u] = v;

        if (depth[u] == depth[v]) {
            ++depth[v];
        }
    }
}

• MST(최소 스패닝 트리) 기본 문제
• 유니온-파인드 자료구조를 이용하면 MST를 쉽게 구할 수 있다.
• 유니온-파인드 구현은 외워두자!