1197 최소 스패닝 트리

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

#Kruskal 알고리즘

1197번: 최소 스패닝 트리

#Kruskal 알고리즘

#1197 최소 스패닝 트리 정리
from sys import stdin

input=stdin.readline

#테스트케이스가 커질수록 standard input이 더 빠릅니다.

 

def get_parents(parents,a):

if parents[a]==a:

return a

parents[a]=get_parents(parents,parents[a])

return parents[a]

#부모 노드가 무엇인지 확인하는 함수

 

def union_parents(arr,a,b):

a=get_parents(arr,a)

b=get_parents(arr,b)

if a>b:

arr[a]=b

else:

arr[b]=a

#서로의 부모 노드를 더 작은 인덱스값을 가진 쪽으로 합치는 함수

def kruskal():

edges=0

answer=0

parents=[i for i in range(v+1)]

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

for start,end,cost in graph:
if get_parents(parents,start)!=get_parents(parents,end):

edges+=1

union_parents(parents,start,end)

answer+=cost

if edges==v-1:

break

return answer

#크루스칼 알고리즘

중요한 점은 parents 노드를 저장할 리스트를 만드는 것, graph를 x[2]을 기준으로 정렬하기 위해 lambda함수를 사용하는 것, edges를 하나씩 입력시킨다는 느낌

v,e=map(int,input().split())

graph=[list(map(int,input().split())) for i in range(e)]

print(kruskal())

 

 

#이전의 벨만포드 알고리즘방식으로 접근했다가 결국에는 답지를 보고만 그런 문제이다.. 이전에 이 문제를 풀었어서 다

른 사람의 코드로 공부한 후 제가 백지에서 다시 작성해보는 식으로 공부했다. 스패닝 트리에 대한 이해와 크루스칼 알

고리즘에 대한 이해가 중요한 문제이다.