[ baekjoon ] 전기가 부족해 10423번 ( python )

문제

백준 10423 전기가 부족해 풀이 ( 파이썬 )

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

10423번: 전기가 부족해

 

 

풀이

Union을 이용하는데 각 발전소 위치를 무조건 parent로 만들기 위해 가장 낮은 숫자로 설정한다.(여기서는 0으로 설정)

그리고 비용이 가장 적게 들어야 하므로 비용이 가장 적은 순서대로 정렬한 후 union parent를 해주면 된다.

# 유니온으로 풀자!
import sys

input=sys.stdin.readline

n,m,k=map(int,input().split())
power=list(map(int,input().split()))

def find_parent(parent,x):
    if parent[x] !=x:
        return find_parent(parent,parent[x])
    return 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

parent=[0]*(n+1)
arr=[]

for i in range(1,n+1):
    # 발전소라면 parent가 0이다
    if i in power:
        continue
    # 발전소가 아니라면 자기자신
    parent[i]=i

for i in range(m):
    s,e,d=map(int,input().split())
    arr.append((s,e,d))

result=0

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

for ele in arr:
    s,e,d=ele
    if find_parent(parent,s)!=find_parent(parent,e):
        union_parent(parent,s,e)
        result+=d

print(result)