최소스패닝트리(크루스칼)

최소 스패닝 트리는 정점이 n개인 상태에서, n-1개의 간선만을 택해 최소 거리를 만든다는 것이 핵심입니다!

최소 스패닝 트리를 만드는 방법은 2가지가 있지만, Kruskal을 이용하여 문제를 풀수있습니다.
이 Kruskal의 구현의 핵심은 Union Find인데
Union Find의 핵심은 친구의 적은 적이라는 것입니다.
같은 그룹으로 만드는 작업 Union과 어느 그룹에 속해있는지를 빠르게 찾는 Find로 이루어져있습니다.

자세한 동작은 여기서 보시면 좋을 것 같습니다

최소 스패닝 트리 관련 글
이미지 등을 첨부하여 내용을 정리하였습니다!

관련 문제 :BOJ 최소 스패닝 트리

by C++

구조체와 compare를 직접 만들고, priority_queue를 이용해 구현하였습니다!!

#include <bits/stdc++.h>
using namespace std;
struct pos{
    int here;
    int next;
    int dist;
};
struct cmp{
    bool operator()(pos &a,pos &b){
        if(a.dist!=b.dist) return a.dist>b.dist;
        if(a.here!=b.here) return a.here>b.here;
        if(a.next != b.next)return a.next>b.next;
    }
};
int Find(int u,int *parent){
    if(u == parent[u]) return parent[u];
    return parent[u] = Find(parent[u],parent);
}
void uni(int u,int v,int *parent){
    u = Find(u,parent), v = Find(v,parent);
    if(u == v) return;
    parent[u] = v;
}
int main() {
    int v,e;
    scanf("%d%d",&v,&e);
    priority_queue<pos,vector<pos>,cmp> pq;
    int *parent = new int[v+1];
    for(int i=0 ;i<=v;i++) parent[i] = i;
    for(int i=0;i<e;i++){
        int here,next,cost;
        scanf("%d%d%d",&here,&next,&cost);
        pq.push({here,next,cost});
    }
    int ans = 0;
    while(!pq.empty()){
        int here = pq.top().here;
        int next = pq.top().next;
        int dist = pq.top().dist;
        pq.pop();
        int heretop = Find(here,parent), nexttop = Find(next,parent);
        if(heretop != nexttop){
            uni(here,next,parent);
            ans += dist;
        }
    }
    printf("%d\n",ans);
    return 0;
}

by Java

PriorityQueue 그리고 Comparator를 아는 것이 핵심입니다!!

import java.io.*;
import java.util.PriorityQueue;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int v = Integer.parseInt(input[0]);
        int e = Integer.parseInt(input[1]);
        int[] parent = new int[v + 1];
        PriorityQueue<p> pq = new PriorityQueue<>((a, b) -> {
            if (a.cost < b.cost) return -1;
            else if (a.cost > b.cost) return 1;
            else {
                if (a.here < b.here) return -1;
                else if (a.here > b.here) return 1;
                else {
                    return 0;
                }
            }
        });
        for (int i = 1; i <= v; i++) parent[i] = i;
        for (int i = 0; i < e; i++) {
            String[] input2 = br.readLine().split(" ");
            int here = Integer.parseInt(input2[0]);
            int next = Integer.parseInt(input2[1]);
            int cost = Integer.parseInt(input2[2]);
            pq.add(new p(here, next, cost));
        }
        int ans = 0;
        while (!pq.isEmpty()) {
            int here = pq.peek().here;
            int next = pq.peek().next;
            int cost = pq.peek().cost;
            pq.poll();
            if (find(here, parent) != find(next, parent)) {
                union(here, next, parent);
                ans += cost;
            }
        }
        System.out.println(ans);
    }

    private static class p {
        int here, next, cost;

        private p(int here, int next, int cost) {
            this.here = here;
            this.next = next;
            this.cost = cost;
        }
    }

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

    private static void union(int u, int v, int[] parent) {
        u = find(u, parent);
        v = find(v, parent);
        if (u == v) return;
        parent[u] = v;
    }
}

궁금하신 사항은 댓글을 남겨주시면 감사하겠습니다^^
잘못 된점 이 있다면 댓글 남겨주시면 감사드리겠습니다