코드

import sys


input = sys.stdin.readline

N = int(input())
M = int(input())

nodes = [i for i in range(N+1)]

def find_root(x):
    if nodes[x] != x:
        nodes[x] = find_root(nodes[x])
    return nodes[x]

def union_root(a, b):
    a = find_root(a)
    b = find_root(b)
    if a < b:
        nodes[b] = a
    else:
        nodes[a] = b


graph = []


for _ in range(M):
    a,b,c = map(int,input().split(" "))
    graph.append([c,(a,b)])

graph.sort()

result = 0

for g in graph:
    w,(a,b) = g

    if find_root(a) != find_root(b):
        union_root(a,b)
        print(nodes)
        result += w

print(result)

풀이

• 전형적인 MST(Minimum Spanning Tree) 문제
• find_root 함수
  - 각 node의 root 값을 찾아서 저장.
  • 초기 node 리스트는 자기 자신을 루트로 가짐.
  • 루트값이 다른 2개의 노드가 엣지로써 제공될 때 (ex: edge = (2,3)), union_root를 통해 root를 통합.
  • 루트가 같다는 것은 cycle이 일어난다는 뜻이기 때문에 패스