[백준] 1922번 네트워크 연결(크루스칼 알고리즘)(Kruskal Algorithm)(Python - 파이썬)

백준 1922번 문제입니다. (solved.ac)기준 골드 4 문제입니다.

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

문제 접근

모든 컴퓨터가 연결되어 있어야하고 최소 비용으로 모든 컴퓨터를 연결하기를 원한다고 합니다.단, a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있다면 a와 c가 연결된다고 합니다. ex) a - b - c최소 신장 트리를 구하는 간단한 문제입니다. 저는 크루스칼 알고리즘을 통하여 구현해보았습니다.크루스칼 알고리즘은 아래 링크에 설명되어있습니다.

2022.03.06 - [정보[Information]] - 신장 트리(Spanning Tree) / 크루스칼 알고리즘(Kruskal Algorithm)(Python - 파이썬)

 

정답 코드

import sys
input = sys.stdin.readline

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

def unionParent(parent, a, b) :
    a = findParent(parent, a)
    b = findParent(parent, b)
    if a < b :
        parent[b] = a
    else :
        parent[a] = b


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

result = 0

parent = [0] * (n+1)
for i in range(n+1):
    parent[i] = i

line = []
for _ in range(m) :
    a, b, cost = map(int, input().split())
    line.append((cost, a, b))

line.sort()

for check in line :
    cost, a, b = check
    if findParent(parent, a) != findParent(parent, b):
        unionParent(parent, a, b)
        result += cost

print(result)