1647 도시 분할 계획1 1647. 도시 분할 계획 (Python) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 신장 트리(MST, Minimum Spanning Tree) 개념을 사용하여 해결할 수 있다. MST를 만들기 위한 알고리즘 중 크루스칼 알고리즘을 사용하였다. 유지비를 오름차순으로 정렬하여 작은것부터 선택하여 사이클이 발생하지 않도록 그래프를 만들어나가면 된다. 원래 N개의 정점이 있는 그래프를 MST로 만들기 위해서는 N-1개의 간선이 필요한데 문제에서는 마을을 두 개의 분리된 마을로 분할한다고 하였다. 그렇기.. 2022. 2. 28. 이전 1 다음
