[Python]최소신장트리 백준 4386

   문제

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

실수 계산에 관해서는 math모듈을 사용하였고  이번에는 프림 알고리즘을 통해 MST를 

구현하였으며 그 과정에서 최소힙을 사용하였다.

Kruskal의 시간복잡도는 각 간선을 정렬하여야 하기 때문에 O(ElogE)이다.

Prime의 시간복잡도는 최소힙을 사용할시  O(ElogV)이다 최소힙을 사용하지 않는다면

 O(V^2)이다.

E의 범위는 V-1<=E<V^2이다.

그래프 내에 적은 숫자의 간선만을 가지고 있을때(희소 그래프)는 Kruskal알고리즘이

 적합하고 그래프 내에 간선이 많이 존재하는 할때(밀집 그래프)는 Prim알고리즘이 

적합하다. 

import sys
import math
import heapq
 
n=int(sys.stdin.readline())
s_location=[]#별위치저장
G=[[] for _ in range(n)]#별들간의 거리
for i in range(n):
    x,y=map(float,sys.stdin.readline().split())
    s_location.append([x,y])
 
# print(s_location)
for i in range(n-1):
    for j in range(i,n):
        # 각 별간의 거리 계산
        dis=round(math.sqrt((s_location[i][0]-s_location[j][0])**2+(s_location[i][1]-s_location[j][1])**2),2)
        if i==j:#자신으로 가는 거리는 계산하지않음
            continue
        #양방향 저장
        G[i].append([dis,j])
        G[j].append([dis,i])
 
#프림 알고리즘을 사용하기 위해 최소힙사용
q=[]
heapq.heappush(q,[0,0])
 
mst_value=0
check=[0 for _ in range(n)]#이어진별 체크
while q:
    dis,end=heapq.heappop(q)
    if check[end]==1:#이미 이어져 있는 별이라면
        continue
    mst_value+=dis#최소거리 갱신
    check[end]=1#이어짐 체크
    for dis,end in G[end]:#해당 별에서 이어진 모든 별 점검
        heapq.heappush(q,[dis,end])
 
 
print(mst_value)