[3124] 최소 스패닝 트리

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE&problemTitle=3124&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

문제 해결 방법

크루스칼 알고리즘을 사용했다.

 

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

public class Solution {
    static int V, E;
    static int[] parent;
    static PriorityQueue<Node> q;

    static class Node {
        int from;
        int to;
        int cost;

        public Node(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }


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

        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            long answer = 0;
            parent = new int[V + 1];
            q = new PriorityQueue<>((n1, n2) -> n1.cost - n2.cost);

            for (int i = 0; i <= V; i++) {
                parent[i] = i;
            }

            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                q.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }

            while (!q.isEmpty()) {
                Node n = q.poll();
                if (find(n.from) != find(n.to)) {
                    union(n.from, n.to);
                    answer += n.cost;
                }
            }
            System.out.println("#" + t + " " + answer);
        }
    }

    private static void union(int from, int to) {
        int parentFrom = find(from);
        int parentTo = find(to);
        parent[parentTo] = parentFrom;
    }

    private static int find(int num) {
        if (parent[num] == num) {
            return num;
        } else return parent[num] = find(parent[num]);
    }
}