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

   문제

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

이번엔 MST알고리즘 중 Kruskal MST 알고리즘을 이용하였다.

Kruskal MST알고리즘은 탐욕 알고리즘으로 가장 가중치가 낮은 간선을 먼저 선택하여 

연결하는데 이때 사이클이 형성 된다면 그 간선을 제외하고 연결한다.

사이클의 형성여부는 유니온 파인드를 통해 검사하였다. 모든 노드가 연결되었다면 멈춘

다.

#모든경로를 오름차순으로 정렬
#방문여부는 유니온파인드를 통해 저장
import sys
 
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
 
 
 
V,E=map(int,sys.stdin.readline().split())
G=[]
p=[i for i in range(V+1)]
 
for _ in range(E):
    A,B,C=map(int,sys.stdin.readline().split())
    G.append([C,A,B])
 
 
 
 
G.sort(key=lambda x:x[0])
#sorted(G)#이렇게 정렬해도 첫번째 인자를 기준으로 정렬하지않는다.
# print(G)
E_count=0#모두 연결되었는지 체크
MST=0#최소스패닝트리의 가중치
for i in range(E):
    dis=G[i][0]
    start=G[i][1]
    end=G[i][2]
    if Find(start)!=Find(end):#루트가 같지않다면 추가할수있다.
        Union(start,end)
        MST+=dis#가중치 업데이트
        E_count+=1
    if E_count==V-1:#모든 노드가 연결
        break
 
print(MST)
 

가장 낮은 가중치를 먼저 선택하기 위해서 오름차순 정렬을 하는데 그냥 sor

ted를 했을경우 첫번째 인자를 기준으로 정렬되는것으로 알고있었으나 위와같

이 2차원 배열일 경우 sort에 정렬 기준을 넣어주어야 제대로 정렬이 된다.