링크 https://www.acmicpc.net/problem/6497 난이도(solved.ac 참고) 골드4 풀이 오랜만에 쓰는 알고리즘 포스팅이다. 이번에는 최소 스패닝 트리의 대표적인 예시인 크루스칼 알고리즘을 사용하여 문제를 풀었다. 크루스칼 알고리즘의 구현 과정은 아래와 같다. 1) 간선 데이터를 비용에 따라 오름차순으로 정렬 2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 2-1) 사이클이 발생하지 않는 경우 최소 스패닝 트리에 포함 2-2) 사이클이 발생하는 경우 최소 스패닝 트리에 포함 X 3) 모든 간선에 대해 2)의 과정을 반복 find_parent 함수를 통해 매개변수 x의 루트 노드를 찾고, union_parent 함수를 통해 두 원소가 속한 집합을 합친다. p..