[백준] 1922 (Java) [MST 알고리즘]

문제

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

 

 

알고리즘

크루스칼 알고리즘

 

 

풀이

가중치가 짧은 순으로 정렬을 해주고

UnionFind를 통해 그래프를 연결해준다.

그 과정에서 가중치를 더하며 정답을 구한다.

 

 

코드

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Test_Cruskal {
    static int N, M;
    static List<Graph> graph;
    static int[] parent;
    static int ans;

    static int getParent(int x) {
        if (parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }

    static void unionParent(int a, int b) {
        a = getParent(a);
        b = getParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    static boolean isSameParent(int a, int b) {
        return getParent(a) == getParent(b);
    }

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

        graph = new ArrayList<>();

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

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.add(new Graph(from, to, w));
        }

        //가중치가 짧은 순으로 정렬(오름차순)
        Collections.sort(graph);

        for (int i = 0; i < graph.size(); i++) {
            int from = graph.get(i).from;
            int to = graph.get(i).to;
            int w = graph.get(i).w;

            //부모가 같지 않다면 연결한다.
            if (!isSameParent(from, to)) {
                ans += w;
                unionParent(from, to);
            }
        }

        System.out.println(ans);
    }

    static class Graph implements Comparable<Graph> {
        int from;
        int to;
        int w;

        public Graph(int from, int to, int w) {
            this.from = from;
            this.to = to;
            this.w = w;
        }

        //정렬시 오름 차순 정렬(가중치가 짧은 순으로)
        @Override
        public int compareTo(Graph o) {
            return w -o.w;
        }
    }
}