백준 1774 : 우주신과의 교감 (Python)

본문 링크

📌 크루스칼 알고리즘

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

N,M=map(int,input().split())

disjoint=[ _ for _ in range(N+1) ]

star=[]

for i in range(N):
    a,b=map(int,input().split())
    star.append((a,b))

edge=[]

for i in range(N-1):
    for j in range(i+1,N):
        edge.append( ( i+1 , j+1 , ((star[i][0]-star[j][0])**2+(star[i][1]-star[j][1])**2)**0.5 ))

edge.sort(key=lambda x:x[2])

total=0

for i in range(M):
    a,b=map(int,input().split())
    a=Find(a)
    b=Find(b)
    if a!=b:
        if a>b:
            disjoint[a]=b
        else:
            disjoint[b]=a

for x,y,value in edge:

    x=Find(x)
    y=Find(y)

    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x
        total+=value

print("%.2f"%total)

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

N,M=map(int,input().split())

visit=[False]*(N+1)
Tree=[ [] for _ in range(N+1)]
check=set()

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

for i in range(M):
    a,b=map(int,input().split())
    check.add((a,b))
    check.add((b,a))

for i in range(1,N):
    for j in range(i+1,N+1):
        if (i,j) in check:
            Tree[i].append((0,j))
            Tree[j].append((0,i))
            continue

        distance=( (star[i][0]-star[j][0])**2 + (star[i][1]-star[j][1])**2)**0.5
        Tree[i].append( (distance,j) )
        Tree[j].append( (distance,i) )



heap=[(0,1)]
total=0

while heap:

    value,node=heapq.heappop(heap)
    if not visit[node]:
        visit[node]=True
        total+=value

        for i,j in Tree[node]:
            heapq.heappush(heap,(i,j))

print("%.2f"%total)

📌 어떻게 접근할 것인가?

전형적인 최소 스패닝 트리 문제입니다. 백준 4386번 과 비슷하게 구현해주시면됩니다.
다만 이미 존재하는 통로에 대해서는 크루스칼 알고리즘은 미리 두 정점을 $Union$ 을 해주고
프림 알고리즘에서는 이미 존재하는 통로애 대해서 가중치를 $0$ 으로 추가했습니다.