개발일지

개념 MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다. => 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것 => 신장트리 : Cycle이 없는 그래프 Kruskal DisjointSet을 이용하여 MST를 갱신하며 구하는 알고리즘 작동원리 1. 모든 간선을 가중치 기준으로 오름차순으로 정렬한다. 2. 가중치가 작은 간선부터 확인하면서 간선에 속한 정점 v1, v2가 다른 SET이면 UNION하고 WEIGHT만큼 RESULT에 더한다. 시간복잡도 간선을 정렬 할 때 : O(ElogE) DisjointSet 사용할 때 : O(1) O(ElogE) 문제 16398 행성 연결 www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 ..