[파이썬] 백준 16562 : 친구비 (골드4)

[파이썬] 백준 16562 : 친구비 (골드4)

• https://www.acmicpc.net/problem/16562
  

---

풀이

방향성 생각

• 기본 유니온 파인드 문제
• 입력을 받아서 부모가 다르면 유니온을 진행한다.
• parent 배열을 바탕으로 각 그룹의 최소 비용을 모두 구한다.
• 최소 비용이 K보다 작으면 비용 출력.

---

전체코드

from collections import defaultdict as dd
import sys

input = lambda : sys.stdin.readline().rstrip()

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

N,M,K = map(int,input().split())
costs = [0] + list(map(int,input().split()))
parent = [i for i in range(N+1)]

for _ in range(M):
    a,b = map(int,input().split())
    pa,pb = find(a),find(b)

    if pa != pb:
        parent[max(pa,pb)] = min(pa,pb)

# 업데이트를 해줘야 오류를 방지할 수 있다. 입력에 따라 업데이트가 안되는 노드 발생함
for p in range(N+1):
    find(p)

table = dd(lambda : float('inf'))
for p,cost in zip(parent,costs):
    table[p] = min(cost,table[p])

req = sum(table.values())
if K >= req:
    print(req)
else:
    print('Oh no')

코멘트

• 쉬운문제