문제 보기 이 문제는 최소 신장 트리(Minimum Spanning Tree) 문제이다. 두 마을로 분리하기 위해서 먼저 최소 신장 트리를 구현하고, 최소 신장 트리를 구성하는 간선 중에 비용이 가장 높은 간선을 제거하였다. 위 과정을 구현하기 위해서 크루스칼 알고리즘을 사용하였다. 1. 입력 받은 간선을 비용을 기준으로 내림차순 정렬을 한다. 2. 비용이 낮은 간선부터 사이클 여부를 확인하고 사이클이 발생하지 않으면 삽입한다. 3. 모든 간선에 대해서 위 과정을 수행한 후 제일 마지막에 삽입한 간선을 제거하였다. 코드 def find_parent(x): if parent[x] != x: parent[x] = find_parent(parent[x]) return parent[x] def union_par..
