https://www.acmicpc.net/problem/1647골드4구현 방법최적화 전"임의의 두 집 사이에 경로가 항상 존재", "비용 양수" 두가지를 통해 최소 스패닝 트리 문제임을 눈치 챘습니다.여기서 추가 조건으로 두개의 그룹을 만들라고 했습니다. 이는 하나의 최소 스패닝 트리를 만들고, 그 트리의 비용들 중 가장 큰 비용를 끊어주면 두 그룹이 나오고, 각각 최소 비용이 된다고 생각했습니다.최소 스패닝 트리는 크루스칼 알고리즘을 통해 구현했습니다. 하지만 꽤 느렸습니다. 따라서 두가지 방법을 통해 최적화 진행 했습니다. 방법1. 트리의 특징을 통한 최적화트리는 (노드 수 - 1)개의 간선을 가지고 있습니다. 현재 문제에서는 하나의 트리에서 간선 하나를 더 끊어서 두 그룹으로 만들면 됩니다.따라서..
