반응형
SMALL
10021 Watering the Fields 파이썬
-
백준 10021번 Watering the Fields알고리즘 2023. 4. 14. 15:27
문제 설명 이번 문제는 여러 좌표에 농지가 있을 경우 이 농지들을 하나로 잇는 관개 시설을 만들 때, 모든 농지들을 포함하는 관개 시설을 짓는 비용의 최소값을 구하는 문제입니다. 좌표가 (ai,aj)인 농지 a와 (bi,bj)인 농지 b 사이의 관개 시설을 짓는 비용은 (ai-bi)^2+(aj-bj)^2 입니다. 문제 풀이 아이디어 트리 모든 농지를 잇는 최소의 비용을 구하기 위해서는 농지를 잇는 간선의 개수를 최소로 해야합니다. 그러므로, 농지를 잇는 간선의 개수는 {농지 개수-1}입니다. 정렬 관개 시설의 전체 비용의 최소값을 찾아야 하므로 비용이 가장 적은 간선부터 포함 여부를 확인해야합니다. 그러므로 비용을 기준 오름차순으로 간선을 정렬해야 합니다. union-find 농지 a와 농지 b를 잇는 ..