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

   문제

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

이 문제는 이미 연결되있는 통로가 있다.

연결된 통로를 제외하고 나머지 연결할수 있는 것들중에서 최소의 통로길이를 구하는 

문제이다.

이전 문제와 달리 오차범위를 허용하지 않는다. 이 부분 때문에 논리상 틀린곳이 없음에

도 코드를 몇번이나 확인하고 틀렸다.

크루스칼을 이용하여 구현하였다.

import sys
import math
 
#크루스칼 알고리즘에 이용할 유니온 파인드
def Find(x):
    if p[x]==x:
        return x
    else:
        y=Find(p[x])
        p[x]=y
        return y
 
def Union(x,y):
    x=Find(x)
    y=Find(y)
    if x!=y:
        p[y]=x
 
 
N,M=map(int,sys.stdin.readline().split())
g_location=[]#신들의 위치
p=[i for i in range(N)]#루트노드 저장
G=[]#간선
 
 
for _ in range(N):#모든 신들의 위치 받기
    x,y=map(int,sys.stdin.readline().split())
    g_location.append([x,y])
 
 
M_count=0#연결된 간선 개수
for _ in range(M):#이미 연결된경우
    god1,god2=map(int,sys.stdin.readline().split())
    if Find(god1-1)!=Find(god2-1):#연결할수 있다면
        Union(god1-1, god2-1)
        M_count+=1
 
 
#거리구하기
for i in range(N-1):
    for j in range(i+1,N):
        # 각 별간의 거리 계산
        #이 문제는 앞전문제처럼 두자리까지만 구하면 안된다. 오차범위를 허용하지 않는다.
        dis = math.sqrt((g_location[i][0] - g_location[j][0]) ** 2 + (g_location[i][1] - g_location[j][1]) ** 2)
        G.append([dis,i,j])
 
 
G.sort(key=lambda x:x[0])
 
result=0
for dis,x,y in G:
    if Find(x)!=Find(y):
        Union(x,y)
        result+=dis#거리추가
        M_count+=1#간선추가
    if M_count==N-1:#간선의 수가 N-1이 되면 멈춘다.
        break
 
 
print("%0.2f" % result)#두자리까지 출력