MST

백준 1197번 C++ 풀이

문제https://www.acmicpc.net/problem/1197시간 제한메모리 제한solved.ac 티어1초128MB골드 4풀이 문제 이름이 정답인 문제다. 최소 스패닝 트리(Minimum Spanning Tree, MST), 최소 신장 트리라고 하는 이 문제는 임의의 그래프가 주어졌을 때, 모든 정점을 최소한의 비용으로 모두 연결하는 알고리즘이다. MST를 구하는 알고리즘은 세가지가 있다. 프림, 솔린, 크루스칼 알고리즘이 있는데, 나는 유니온파인드 자료구조도 같이 공부할 겸 크루스칼을 공부한 상태이다. 크루스칼 알고리즘은 나중에 언젠가 정리하겠지만, 간단하게 설명하면 모든 정점을 유니온파인드 자료구조에서 루트노드인 상태, 그러니까 미연결상태로 둔 뒤, 간선의 가중치를 오름차순으로 정렬한다. 간선..