[BOJ] 16562. 친구비

www.acmicpc.net/problem/16562

16562번: 친구비

문제: 준석이가 돈을 내고 친구를 구하는데, 친구의 친구도 친구가 된다. 최소비용으로 모든 친구를 사겨라.

 

요즘 최소 스패닝 트리에 대해 다시 리마인드하는 차에 크루스칼 알고리즘의

부모 격인 유니온 파인드 문제들을 풀어보고 있습니다.

거기서도 대표 문제 격인 "친구비" 문제입니다.

사실 문제 이해하는 단계를 지나 알고리즘 분류를 통해 들어갔기 때문에 이해 단계를 생략합니다.

 

문제 풀어보기!!

이 문제는 한번만에 바로 풀었는데 유니온 파인드에서

최소 비용 리스트 하나만 더 추가해주면 되었기 때문입니다.

기본적인 find()함수와 union() 함수를 만들고 그 안에서 부모를 찾을 때마다

최소 값을 비용 리스트에 갱신시켜 줍니다.

그리고 모든 친구들의 부모를 찾아서 다른 부모일 때만 그 부모의 비용 값을 더합니다.

그렇게 나온 값이 자신이 가지고 있는 돈보다 작으면 해당 비용을 출력.

(해당 비용은 최소비용이기 때문입니다.)

자신이 가지고 있는 돈보다 크다면 "Oh no"를 출력하면 됩니다.

 

코드:

from sys import stdin
input = stdin.readline

def find(x):
    if x == friends[x]:
        return x
    else:
        if arr[friends[x]] > arr[x]:
            arr[friends[x]] = arr[x]
        else:
            arr[x] = arr[friends[x]]
        friends[x] = find(friends[x])
        return friends[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if arr[x] > arr[y]:
        arr[x] = arr[y]
    else:
        arr[y] = arr[x]
    if x < y:
        friends[y] = x
    else:
        friends[x] = y

N, M, k = map(int, input().split())
friends = [i for i in range(N+1)]
arr = [0] + list(map(int, input().split()))
for i in range(M):
    a, b = map(int, input().split())
    union(a, b)

tmp = set()
cnt = 0
for i in range(1,N+1):
    a = find(i)
    if a in tmp:
        continue
    else:
        tmp.add(a)
        cnt += arr[a]

if cnt <= k:
    print(cnt)
else:
    print("Oh no")