[코드트리/NOVICE HIGH] MST 찾기 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] parent = {0,1,2,3,4,5,6,7};
    static PriorityQueue<Node> pq;
    
    public static void main(String[] args) throws IOException {
        pq = new PriorityQueue<>();
        
        pq.add(new Node(1, 2, 19));
        pq.add(new Node(1, 3, 13));
        pq.add(new Node(1, 5, 14));
        pq.add(new Node(1, 4, 30));
        pq.add(new Node(1, 7, 54));
        
        pq.add(new Node(2, 3, 12));
        pq.add(new Node(2, 6, 29));
        
        pq.add(new Node(3, 5, 23));
        pq.add(new Node(3, 6, 17));
        
        pq.add(new Node(4, 7, 28));
        pq.add(new Node(5, 7, 76));
        pq.add(new Node(6, 7, 49));
 
        
        // MST 수행
        int useEdge = 0;
        int result = 0;
        
        while(useEdge < 6) {
            Node now = pq.poll();
            
            if(find(now.s) != find(now.e)) { // 간선 이룬 두 노드가 다른 경우에만
                union(now.s, now.e); // 둘이 같은 노드 갖도록 함
                result += now.v;
                useEdge++;
            }
        }
        
        System.out.println(result);
    }
    
    // 유니온 파인드
    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) parent[b] = a;
    }
    
    static int find(int a) {
        if(a == parent[a])  return a;
        return parent[a] = find(parent[a]); // 경로 압축
    }
    
}
 
class Node implements Comparable<Node> {
    int s, e, v;
    
    public Node(int s, int e, int v) {
        this.s = s; this.e = e; this.v = v;
    }
    
    // 가중치 오름차순 정렬
    @Override
    public int compareTo(Node node) {
        return this.v - node.v;
    }
}

 

---

💬 느낀 점

크루스칼 오랜만에 보니 다 잊음.... 복습하자 복습

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

최소 신장 트리 (MST)