링크 https://www.acmicpc.net/problem/1647 난이도(solved.ac 참고) 골드4 풀이 최소 스패닝 트리와 크루스칼 알고리즘을 공부한 뒤에 가볍게 풀어본 문제인데, 재밌었다. 최소 스패닝 트리는 하나의 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이며 가중치의 합이 최소인 그래프이다. 그리고 이 최소 스패닝 트리에 관한 알고리즘으로는 크루스칼 알고리즘이 있다. 크루스칼 알고리즘은 그래프에서 A와 B를 선택했을 때 A에서 B로 가는 경로가 반드시 존재하도록 최소 비용으로 간선을 배치하는 경우의 수에 관한 알고리즘이다. 이 알고리즘의 지향점은 당연히 최소 스패닝 트리를 만족하면서 가중치의 합이 최소가 되게끔 하는 것이다. 일반적인 크루스칼 알고리즘의 기본 ..