문제 : https://www.acmicpc.net/problem/1197
최소 스패닝 트리를 이용해 푸는 문제이다.
크루스칼 알고리즘을 이용했다.
import sys
input=sys.stdin.readline
V,E=map(int,input().split())
li=[]
cnt=0
weight=0
nodes=[i for i in range(V+1)] # 노드의 수만큼 배열 생성
for i in range(E): #간선정보 입력
A,B,C=map(int,input().split()) # A와 B가 가중치 C로 연결
li.append([A,B,C])
def find(a): # a노드의 루트노드를 찾는 과정
if nodes[a]==a:
return a
else:
nodes[a]=find(nodes[a])
return nodes[a]
def union(a,b): # a와 b노드를 합치는 과정
a=find(a)
b=find(b)
if a!=b: # a와 b의 루트노드가 다른 노드일 경우
if a<b: # a의 루트노드가 b보다 작을경우
nodes[b]=a # a의 아래에 b를 단다
else:
nodes[a]=b
li.sort(key=lambda x:x[2]) # 가중치 오름차순으로 정렬
i=0
while cnt<V-1:
a,b,v=li[i][0],li[i][1],li[i][2]
if find(a)!=find(b):
cnt+=1
weight+=v
union(a,b)
i+=1
print(weight)