🔍 필요 배경 지식

가. Spaning Tree
모든 그래프가 연결되어 있는 트리로 사이클이 없어야 한다.

span : 걸치다
모든 노드를 걸친다는 것은 모든 노드가 연결되어 있다는 의미이다.

나. MST(Minimum Spanning Tree)
Spanning Tree에서 모든 간선 가중치의 합이 최소가 되는 트리이다.

구현방법
1. 크루스칼 (유니온 파인드 사용)
가장 작은 간선부터 찾아 노드들을 연결한다. 만약 사이클이 형성되면 연결하지 않는다.

2. 프림
   현재 노드에서 가장 작은 간선을 선택하고 그 간선과 이어진 노드를 연결한다.

다. Comparable<자료형>
자바에서 객체를 정렬할 수 있게 해주는 인터페이스로 이를 사용하여 클래스를 구현하면

compa

---

📒 크루스칼 알고리즘 기반 MST구현 과정

가. Edge Class

static class Edge implements Comparable<Edge> {
        int n;
        int m;
        int weight;

        Edge(int n, int m, int weight) {
            this.n = n;
            this.m = m;
            this.weight = weight;
        }


        @Override
        public int compareTo(Edge e) {	
            return this.weight - e.weight; //이 부분 변경하여, 최소힙, 최대힙 결정 가능
        }

}

compareTo : 현재 Edge가 this이고 대상 엣지가 e이다. 참고로 우선순위 큐에서 add를 진행할 시, 넣을 Edge가 this가 되고 넣을 때, 앞의 이미 들어간 Edge들과 비교를한다. 이때 해당 함수를 사용하게 되고 this와 기존에 있던 edge들을 해당 함수의 파라미터로 넣는다. 만약 Return 값이 음수이면 this와 이전값 자리를 바꾸게 되고 양수이면 그냥 납둔다. 즉, 현재들어온 this가 기존에 있었던 e보다 작으면 자리를 바꾸게 되므로 최소힙에서 작은 값이 더 트리의 위로 올라가는 것이다. 이렇게 우선순위큐로 최소힙을 구현할 수 있다.

나. 작은 가중치 가진 간선의 붙일 노드 선정하고 그래프에 연결

1. 작은 가중치
   우선순위 큐를 사용하여 가중치가 작은 순으로 간선정보를 큐에 넣은뒤, 큐가 빌때까지 하나씩 꺼낸다.

2. 노드끼리 연결
   위에서 간선꺼내고 각 노드들을 이어 붙일 때, 노드가 연결되어있는지 확인하고 연결되어 있지 않으면 이어붙이고 아니면 무시한다.

3. 가중치합 구하기
   위에서 각 노드들을 이어 붙일 때, 간선의 누적합을 갱신한다.

다. Edge Class

1. Union

static void union(int[] parent, int a, int b) {
        a = find(parent, a);
        b = find(parent, b);

        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

2. Find

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

        return parent[n] = find(parent, parent[n]);
    }

라. 전체 코드

import java.util.*;
import java.io.*;
import java.lang.*;

public class MST {
    static Scanner sc = new Scanner(System.in);

    static class Edge implements Comparable<Edge> {
        int n;
        int m;
        int weight;

        Edge(int n, int m, int weight) {
            this.n = n;
            this.m = m;
            this.weight = weight;
        }


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


    public static void main(String args[]) throws IOException {
        PriorityQueue<Edge> que = new PriorityQueue<>();
        int node_cnt;
        int edge_cnt;
        int[] parent;
        int w_sum = 0;

        node_cnt = sc.nextInt();
        edge_cnt = sc.nextInt();

        parent = new int[node_cnt + 1];

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

        for (int i = 0; i < edge_cnt; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int w = sc.nextInt();

            que.add(new Edge(n, m, w));
        }

        while (!que.isEmpty()) {
            Edge e = que.poll();
            if (find(parent, e.n) != find(parent, e.m)) {
                union(parent, e.n, e.m);
                w_sum += e.weight;
            }
        }


        System.out.println(w_sum);

    }

    static void union(int[] parent, int a, int b) {
        a = find(parent, a);
        b = find(parent, b);

        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

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

        return parent[n] = find(parent, parent[n]);
    }
}

---

🤔 느낀점

크루스칼이 프림보다 상대적으로 구현하기 쉬운 것 같다.