BaekJoon 1197번 : 최소 스패닝 트리 (python)

BaekJoon 1197번 : 최소 스패닝 트리 (G4 41.216%)

최소 스패닝 트리 문제

크루스칼 알고리즘을 이용한 기본 문제이다.

• 크루스칼 알고리즘을 이용하여 입력받은 두 정점과 가중치를 가중치가 낮은 순서대로 정렬하여 가중치가 낮은 순서대로 간선을 잇는 작업을 진행해준다.
• 만약 이미 root노드가 같은 상태라면 진행하지 않겟지만 root노드가 다른 상황이라면 두 부분집합을 합쳐주어 root노드를 통일시켜주고 해당 길을 잇기 위해 가중치를 더해준다.
• 이를 통해 모든 노드를 잇는 하나의 부분집합을 만들 수 있고 해당 부분집합은 최소의 가중치로 이어진 부분집합이 되게 된다.

import sys
input = sys.stdin.readline
#sys.setrecursionlimit(10**5)

def find(x) :
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

def union(x,y) :
    rootx = find(x)
    rooty = find(y)

    if rootx > rooty :
        root[rooty] = rootx
    else :
        root[rootx] = rooty

V, E = map(int,input().split())

root = list(i for i in range(V+1))
edges = list()
result = 0
for _ in range(E) :
    a, b, cost = map(int,input().split())
    edges.append((cost,a,b))

edges.sort()
for i in edges :
    cost, a, b = i[0], i[1], i[2]
    if find(a) != find(b) :
        union(a,b)
        result += cost
print(result)