[python] 백준 1922: 네트워크 연결

 

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

 

노드와 간선을 활용하여 비용의 합을 구하고, 출력하는 문제이다.

 

"최소 스패닝 트리" 라는 문제라고 한다. 해당 문제를 풀기 위한 알고리즘은  "크루스칼 알고리즘" 이라고 함.

 

간선을 비용 순서로 정렬하여, 비용이 작은 간선부터 사이클이 생기지 않도록 연결하고, 사이클을 감지하는 식으로 진행한다.

 

#백준 1922: 네트워크 연결

import sys

input = sys.stdin.readline

def find_parent(parent, x):

if parent[x] != x: #if parent[x] != x:

parent[x] = find_parent(parent, parent[x]) #parent[x] = find_parent(parent, parent[x])

return parent[x]

def union_parent(parent, a, b):

a = find_parent(parent, a)

b = find_parent(parent, b)

if a < b:

parent[b] = a

else:

parent[a] = b

#input(node(n), edge(m))

n = int(input())

m = int(input())

#initialize

parent = [0] * (n + 1) #dp

cost = [] #edge

result = 0 #result init

for i in range(1, n + 1): #parent init

parent[i] = i

 

for _ in range(m): #edge input

a, b, c = map(int, input().split())

cost.append((c, a, b))

 

cost.sort()

for c, a, b in cost: #edge

if find_parent(parent, a) != find_parent(parent, b):

union_parent(parent, a, b)

result += c

 

print(result)