[Python] BOJ 1647 - 도시 분할 계획
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 # 무난한 MST문제이다. 마을을 두개의 마을로 분리하면서 남은 길들의 유지비가 최소가 되어야 하므로 크루스칼 알고리즘으로 최소 간선들로만 모든 집을 연결 한 뒤 가장 비용이 큰 길 하나만 없애면 된다. # 27 ~ 31줄 반복문에서 last는 항상 g[2]로 갱신되는데 graph가 비용순으로 오름차순 정렬되어 있으므로 결국 마지막 last에는 가장 비용이 큰..
