(python) 백준 16562 - 친구비

백준 16562

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

16562번: 친구비

 

1. 문제 설명

 

특정 비용을 지불하여 친구를 사귀며 친구의 친구를 친구로 인정한다.

 

친구 전부를 사귈 수 있는 최소 비용을 구하는 문제

 

2. 문제 풀이

 

한 친구를 사귄다면 다른 친구 또한 사귀게 되는 원리이다.

 

그러므로 친구 관계를 형성하는 번호끼리 구분을 해줄 필요가 있다.

 

유니온 - 파인드 알고리즘을 활용하여 최소비용을 구하는 문제이기에

비용이 적은 번호를 기준으로 합친다.

 

더 적은 비용의 번호가 부모노드가 되며 다른 노드의 비용은 0으로 초기화한다.

(친구의 친구는 친구가 된다는 원리로 인하여)

 

아래는 유니온 - 파인드 알고리즘이다.

 

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]

def union(x,y):
    x_parent = get_parent(x)
    y_parent = get_parent(y)
    if cost[x_parent] > cost[y_parent]:
        cost[x_parent] = 0
        parent[x_parent] = y_parent
    else:
        cost[y_parent] = 0
        parent[y_parent] = x_parent

 

3. 전체 코드

 

def get_parent(x):
    if parent[x] == x:
        return x
    parent[x] = get_parent(parent[x])
    return parent[x]

def union(x,y):	#더 작은 비용을 기준으로 병합
    x_parent = get_parent(x)
    y_parent = get_parent(y)
    if cost[x_parent] > cost[y_parent]:
        cost[x_parent] = 0
        parent[x_parent] = y_parent
    else:
        cost[y_parent] = 0
        parent[y_parent] = x_parent

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

cost = [0]  #친구비 리스트
for c in list(map(int, input().split())):
    cost.append(c)

parent = [i for i in range(n+1)]    #부모 노드 저장할 리스트

for _ in range(m):
    v, w = map(int, input().split())
    union(v, w)

total_cost = sum(cost)
#총 비용이 예산보다 크다면 친구 다 사귈 수 없다.
if total_cost <= k:
    print(total_cost)
else:
    print("Oh no")