풀이 N개의 집들에 대해 2개의 그룹으로 나누고, M개의 길에 대해, 유지비가 최솟값이 되도록 집들을 연결해주면 된다. 단순하게 접근해보자. Minimum Spanning Tree 문제를 풀이할 때, N개의 정점에 대해서 가중치를 기준으로 미리 정렬된 N - 1개의 간선으로 모든 정점을 연결할 수 있다는 사실을 알고있다. 그렇다면, N개의 집들을 2개의 그룹으로 나누는 가장 단순한 방법은 무엇일까? 바로, N - 2개의 간선만 이용해 N - 1개의 정점을 연결해주면 된다. 가중치에 대해 오름차순으로 정렬하고, 최소 가중치를 우선적으로 연결하는게 이득인점을 이용한 풀이다. 소스코드 소스코드 보기 출처 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,00..
