코딩 잘하고 싶어

그래프 문제로 어려운 난이도는 아니지만 좋은 문제 같아서 정리해보려한다. 풀이를 생각하는 과정이 마음에 들었다. https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 마을 안의 도시끼리 한 길로만 연결되고 나머지 길은 없앨 수 있다는 점에서 최소 스패닝 트리를 생각했다. 크루스칼 알고리즘을 사용하여 풀 수 있다. 유지비를 최소로 하기 위해서 정렬 후 유지비가 작은 길부터 크루스칼 알고리즘을 사용하면 된다. 그런데..