백준 1197 최소 스패닝 트리

중요 idea:

• edgelist.append((edge, V1, V2))
• edge.sort(key=lambda x:x[0])

(간선, 노드1, 노드2) 로 입력받고, 간선을 오름차순으로 정렬 해놓는다.
-> 입력값에 1 2 10 // 2 1 1 등 이상한 테스트케이스 방지해서 최소 스패닝트리를 충족시키기 위해.

• find(V)
  -> 부모노드 누구인지 재귀적으로 확인, 초기값은 자기자신.
  -> 경로 압축 스킬
  -> parent[i] = find(parent[i])
  -> 참고로 return 값으로 재귀를 돌리면 더오래걸린다.

• union(V1, V2)
  -> parent = [ 0, 1, 2, . . . V]
  노드가 1~V 까지 있으므로, parent 배열을 만들어놓고, 연결된 노드가 있을 때마다 작은 값을 부모 노드로 최신화시킨다.

import sys

V, S = map(int, sys.stdin.readline().split())

edge = []
for _ in range(S):
    a, b, w = map(int, sys.stdin.readline().split())
    edge.append((w, a, b))
edge.sort(key=lambda x: x[0])
parent = list(range(V + 1))


# range 1~ 안댐


def connect(a, b): # union(V1, V2)
    a = check(a)
    b = check(b)

    if b < a:
        parent[a] = b
    else:
        parent[b] = a


def check(a): # find(V)
    if a == parent[a]:
        return a
    parent[a] = check(parent[a])  # 경로 압축
    return parent[a]  # check(parent[a])


sum = 0
for w, s, e in edge:
    if check(s) != check(e):
        connect(s, e)
        sum += w

print(sum)