[BOJ/백준] 네트워크 연결 1922 gold4 / 크루스칼 알고리즘 / python

✨ 문제

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

이 문제에서 '모든 컴퓨터를 연결하는데 필요한 최소비용'를 보고 크루스칼 알고리즘을 떠올렸다.
크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)
크루스칼 알고리즘은 모든 노드를 사이클이 발생하지 않는 형태로 연결하며 가장 적은 비용으로 모든 노드를 연결하고 싶을 때 사용하는 알고리즘이다!

✨ 내 코드

import heapq
node=int(input())
edge=int(input())

graph=[i for i in range(node+1)]

def find_parent(x):
    if graph[x]!=x:
        graph[x]=find_parent(graph[x])
    return graph[x]

def union(a,b):
    a,b=find_parent(a),find_parent(b)
    if a<b:
        graph[b]=a
    else:
        graph[a]=b

q=[]
for _ in range(edge):
    a,b,c=map(int,input().split())
    heapq.heappush(q,(c,a,b))

res=[]
while q:
    c,a,b=heapq.heappop(q)
    if find_parent(a)!=find_parent(b):
        res.append(c)
        union(a,b)

print(sum(res))

크루스칼 알고리즘 구현 시 입력값으로 받은 a,b,c (a->b까지의 거리 c) 에서 거리를 기준으로 오름차순으로 정렬 후 순차적으로 거리가 짧은 간선부터 사이클 판별을 하게 되는데, 나는 이 부분에서 우선순위 큐로 짧은 노드부터 꺼내는게 sort()하는 방법보다 시간복잡도 측면에서 더 효율적일거라고 판단해서 heapq 라이브러리를 사용해서 우선순위 큐를 구현했다.