Lake_Light

import java.io.*; import java.util.*; public class Main { public static class Lecture implements Comparable { int start; int end; public Lecture(int start, int end) { this.start = start; this.end = end; } public int getStart() { return start; } public int getEnd() { return end; } // 수업 시작 시간을 기준으로 오름차순 정렬 || 수업 시작 시간이 같다면 종료 시간 기준 @Override public int compareTo(Lecture o) { if(o.getStart()==getS..

Spanning Tree 그래프 내의 모든 정점을 포함하면서 순환이 존재하지 않는 간선을 최소로 하는 최소 연결 부분 그래프를 의미합니다. [간선의 수: n-1개, Cycle 존재 X] Minimum Spanning Tree (MST) 특정 그래프의 Spanning Tree 중에서 간선들의 가중치의 합이 최소가 되는 Spanning Tree를 말합니다. MST를 만드는 알고리즘은 대표적으로 크루스칼(Kruskal), 프림(Prim) 두 가지가 있습니다. 크루스칼 알고리즘 모든 간선을 가중치 기준으로 오름차순으로 정렬하고, 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하는 것입니다. 이 때 서로소 집합(disjoint set) 자료구조의 Union, Find 연산을 사용하여 순환(Cycle) 이 형..