import sys
input = sys.stdin.readline
from heapq import heappush,heappop
def findparent(x):
if parent[x] == x:
return x
parent[x] = findparent(parent[x])
return parent[x]
V,E = map(int,input().split())
hq = []
for i in range(E):
x1,x2,w = map(int,input().split())
heappush(hq,(w,x1,x2))
parent = {i:i for i in range(1,V+1)}
result = 0
while hq:
w,x1,x2 = heappop(hq)
if findparent(x1) == findparent(x2):
continue
parent[findparent(x1)] = findparent(x2)
result += w
print(result)최소 스패닝 트리 알고리즘의 가장 기초적인 문제이다.
어떻게 풀어야 할지 며칠동안 고민해도 답이 안나와서 끙끙댔었는데, 크루스칼 알고리즘 설명을 읽으니까 1분만에 풀 수 있었다.
최소 스패닝 트리 설명은 https://ssabi.tistory.com/60
[알고리즘] 최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리(Minimum Spanning Tree) 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미합니다. n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 됩니
ssabi.tistory.com
여기에 친절하게 나와있다.
전에 다 익스트라 문제를 풀었을때도 느꼈지만 모르는 알고리즘 문제는 고집부리지말고 빨리 답지 보는게 맞다
이번 문제는 크루스칼 알고리즘을 썼는데, 최소 신장 트리 문제는 프림 알고리즘으로 풀 수도 있다고 하니 다른 문제에서 고려해야할 것이다.
오늘의 교훈) 고집피우지 말자