[백준] 1922 파이썬 - 네트워크 연결

문제

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

풀이

최소 신장 트리를 구하는 간단한 문제였다.

 

오늘 다른 최소 신장 트리 관련 문제(아래 링크)를 풀어서 쉽게 풀 수 있었다.

[백준] 1647 파이썬 - 도시 분할 계획

 

코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

graph = []
parent = list(range(n+1))
for _ in range(m):
    a,b,c = map(int,input().split())
    if a!=b:
        graph.append((c,a,b))

graph.sort()

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

def union(a,b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def solution():
    answer = 0
    for c,a,b in graph:
        if find(a) != find(b):
            union(a,b)
            answer += c
    return answer


print(solution())