[BOJ]1922 네트워크 연결 파이썬 풀이

N = int(input())

M = int(input())

import sys

input = sys.stdin.readline

print = sys.stdout.write

result = 0

#a, b, cost

edges = [list(map(int, input().split())) for _ in range(M)]

edges.sort(key=lambda x: x[2])

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

def find(x):

    if parent[x] != x:

        parent[x] = find(parent[x])

    return parent[x]

def union(a, b):

    a = find(a)

    b = find(b)

    if a > b:

        parent[a] = b

    else:

        parent[b] = a

for edge in edges:

    a, b, cost = edge

    if find(a) != find(b):

        union(a, b)

        result += cost

print(str(result))

정말 기본적인 MST를 이용하여 풀이하였다.

표준 입출력 사용해야 python으로 제출했을때 시간초과가 발생하지 않는다.

시간복잡도 O(E log E)