[백준/16562/파이썬] 친구비

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

16562번: 친구비

Problem

• 19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다.
• 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다! 
• 위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

조건

• 학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다.
• 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다
• 준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

SOL

 친구를 하려면, 친구비를 내야하는 가혹한 현실을 반영한 문제이다. 여기서 핵심은, "친구의 친구는 친구다" 즉, A-B,B-C가 친구관계를 형성한다면, A-B-C는 모두 친구관계라고 생각한다는 거다. 이 문제는 친구관계인 경우에는, 돈을 추가로 안줘도 되는걸 파악하는게 핵심이다.

그림판

Cost = [10,10,30,20,50] 이고, 이와 같이 친구관계가 형성되어있다고 하자.

그럼, 내가 내야하는 최소비용의 친구비는 (10 +30) = 40이다.

즉, 친구들 중에서, 가장 비용이 적은 친구에게만 주면 된다는 거다

 

친구 관계를 형성할 때,  Union -Find 구조를 이용해줄거다.

 

이때, union을 해줄 때, Cost가 작은 곳이 root가 되게끔 union을 해주면 효율적으로 구현이 가능할 것 같다.

(만약, 통상적인 Union-Find를 쓴다면, if문을 통해서 특정 조건을 주렁주렁 달거나, 2중 반복을 사용해서, 친구 리스트를 만들고, 그 중에 최솟값을 갱신시키고 마지막에 update를 해주는 방법 등이 있을 수 있겠다.)

 

import sys
input = sys.stdin.readline

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

def find(target):
    if target==parent[target]:
        return target
    parent[target] = find(parent[target])
    return parent[target]

def union(a,b):
    a=find(a)
    b=find(b)
    if a !=b:
    	# 친구관계를 형성할 때, root를 비용이 적은 친구로 한다.
        if costs[a] <=costs[b]:
            parent[b] = a
        else:
            parent[a] =b
#친구관계 형성
for i in range(M):
    v,w =map(int,input().split())
    union(v,w)
#최소비용이 드는 친구 찾기
ans=0
for idx,root in enumerate(parent):
    if idx ==root:
        ans+=costs[idx]

if ans<=K:
    print(ans)
else:
    print("Oh no")