[BOJ] 4386. 별자리 만들기 (🥇, MST)

🔗

풀이

모든 별들을 최소 연결해야 하는데 최소 비용이여야 함 -> 최소 스패닝 트리

좌표들 간의 거리가 곧 비용이기 때문에 모든 좌표에 대해서 다른 좌표들과의 거리 값을 전부 구해서 거리에 대해 오름차순으로 정렬하고 크루스칼 알고리즘으로 풀이

주어지는 좌표들의 개수는 최대 100개이기 때문에 모든 좌표 값을 계산하는데는 100*100으로 만 번의 연산만 수행하면 됨. 연산 수행의 결과에 대해 distance 배열에 저장하고 오름차순 정렬 후, 분리집합 개념을 사용해서 같은 집합에 속해있는지 확인. 같은 집합이라면 이미 연결되어 있고, 같은 집합이 아니라면 아직 연결되어 있지 않으므로 연결. 연결했다면 비용을 계산해야 하므로 비용(거리)을 더해줌.

def calc_dist(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x = parent[x]
    y = parent[y]

    if x < y:
        parent[y] = x
    else:
        parent[x] = y

n = int(input())
lines = [list(map(lambda x: int(float(x) * 100), input().split())) for _ in range(n)]
parent = [i for i in range(n)]

distance = []
for i in range(n):
    for j in range(n):
        distance.append((i, j, calc_dist(*lines[i], *lines[j])))

distance.sort(key=lambda x: x[2])
count = 0
for a, b, d in distance:
    if find(a) != find(b):
        union(a, b)
        count += d

print(int(count)*0.01)