백준 10021 Watering the Fields

https://www.acmicpc.net/problem/10021

이 문제는 정점들과 정점들 사이의 비용을 주어준 문제이다.
요구사항은 이 간선들중에서 최소비용으로 사이클 없는 그래프를 만드는 것인데, 크루스칼 알고리즘을 사용하여 이 문제를 해결할 수 있다.

크루스칼 알고리즘은 그래프 내에 모든 정점들을 최소비용으로 연결하는 알고리즘을 말한다. 즉 최소신장트리를 구하기 위해 사용되는 알고리즘이다.

크루스칼 알고리즘에서는 사이클을 그리지 않게 하는것이 중요한데, 이 때 union-find를 사용한다.

union함수는 두 정점을 연결해 주는 함수를 뜻하고, 주로 값이 작은 정점이 부모가 되게 한다. ex) parent[a] = b ## a의 부모노드는 b이다.

find함수는 어떤 정점의 가장 최상단에 있는 부모를 찾아주는 함수이다.
가장 최상단의 부모는 자기 자신을 부모노드로 가지기 때문에 재귀를 통해서 자신의 부모노드의 부모노드를 재귀를 통해 찾는 방식을 이용해 가장 최상단까지 올라갈 수 있다.

from itertools import combinations
import heapq
n,c = list(map(int,input().split()))
def getDistance(ax,ay,bx,by):
    r1 = abs(ax-bx)
    r2 = abs(ay-by)
    return r1**2 + r2**2
def find(node):
    if parent[node] == node:
        return node
    parent[node] = find(parent[node])
    return parent[node]
def union(a,b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

locations = []
for i in range(n):
    locations.append(list(map(int,input().split())))

cases = list(combinations(range(n),2))
parent = [i for i in range(n)]
heap = []
for case in cases:
    dist = getDistance(locations[case[0]][0],locations[case[0]][1],locations[case[1]][0],locations[case[1]][1])
    if dist >= c:
        heapq.heappush(heap,(dist,case))
cnt = 0
ans = 0
while len(heap) > 0 and cnt < n-1:
    dist,case = heapq.heappop(heap)
    if find(case[0]) != find(case[1]):
        cnt += 1
        ans += dist
        union(case[0],case[1])

ans = -1 if cnt != n-1 else ans
print(ans)