[BOJ] 16562. 친구비 (🥇, 분리 집합)

🔗

풀이

준석이는 최소한의 비용으로 친구를 사귀고 싶어한다. 친구의 친구는 친구라는 것은 결국 1, 2가 친구고 1, 3이 친구라면 2, 3 역시 친구가 된다는 소리다. 결국 친구 관계를 하나의 집합으로 묶을 수 있다. 분리집합 개념을 사용할 수 있을 것 같다. 보통 분리집합에서는 숫자가 작은 값을 대표로 사용하지만 여기서는 최소 비용이 목적이기 때문에 친구비가 적은 값을 대표로 사용하기로 한다.

모든 친구 관계를 탐색하며 각자 이루는 집합을 만든 후에 최종적으로 대표하는 값들이 무엇인지를 찾는다. 이때 대표 값들은 애초에 최소 비용으로 설정해두었으므로 이 값들에 해당하는 친구비들을 더해나간다. 더하는 도중에 준석이가 갖고 있는 돈 k를 넘어선다면 모두와 친구를 할 수 없는 것이므로 "Oh no"를 출력한다.

import sys
input = sys.stdin.readline

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

def union(x, y):
    x = find(x)
    y = find(y)
    
    if A[x] <= A[y]:
        rep[y] = x 
    else:
        rep[x] = y

N, M, K = map(int, input().split())
A = [0]+list(map(int, input().split()))
rep = [i for i in range(N+1)]
for _ in range(M):
    v, w = map(int, input().split())
    if find(v) == find(w):
        continue
    union(v, w)

rep_lst = list(set(find(i) for i in range(1, N+1)))
cost = 0
for x in rep_lst:
    cost += A[x]
    if cost > K:
        print("Oh no")
        exit()
print(cost)