1647번 (1) 썸네일형 리스트형 [크루스칼] 백준 1647번 '도시 분할 계획' (Python) 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 1. 모든 노드를 포함하면서 사이클이 존재하지 않고, 최소비용으로 신장트리를 만들어야 하므로 크루스칼 알고리즘 적용 2. 비용순으로 간선 정렬 3. 사이클이 발생하지 않는 경우에만 집합 합치기 4. 최소 신장트리를 구성하는 간선 중에서 가장 비용이 큰 간선 제거 def find_parent(parent, x): if parent[x]!=x: parent[x] .. 이전 1 다음