[파이썬] 백준 4386 : 별자리 만들기 (골드3)

[파이썬] 백준 4386 : 별자리 만들기 (골드3)

백준 4386 : 별자리 만들기 (골드3)

---

풀이

방향성 생각

• MST

코드

N = int(input())

arr = [list(map(float,input().split())) for _ in range(N)]
G = []
for i in range(N-1):
    ax,ay = arr[i]
    for j in range(i+1,N):
        bx,by = arr[j]
        dist = ((ax-bx)**2+(ay-by)**2)**0.5
        G.append((dist,i,j))
G.sort()

P = [i for i in range(N)]
def find(x):
    if x != P[x]:
        P[x] = find(P[x])
    return P[x]

answer = 0
for cost,x,y in G:
    px = find(x)
    py = find(y)
    if px != py:
        answer += cost
        P[max(px,py)] = min(px,py)
print(f"{answer:.2f}")

코멘트

*