BOJ 16562 친구비

BOJ 백준 16562 C++

친구비

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

 

 

친구비..

 

 

1) union-find 약간 변형된 문제

2) 기본 union-find를 풀 듯이, 처음에 모든 node의 부모를 자기 자신으로 설정했다.

그리고 M번 동안 친구 관계를 입력받으면서, 친구(부모가 같은 하나의 집합)가 아니라면 unite()함수를 실행한다.

<포인트>는 unite()의 line 30-31에서 부모를 같게 만들 때, 가장 적은 비용으로 친구를 만들기 위해서 비용이 큰 node의 부모를, 작은 node의 부모로 바꿔준다. 

3) 친구 관계를 정리 한 후, 모든 학생과 친구가 되었는지 확인 하기 위해 check[]를 이용하여 확인 했다.

4) 개인적으로 union-find 문제 풀 때마다 드는 생각은 참 재미있는 알고리즘이다. 집합의 개념을 이렇게도 활용할 수 있구나!

 

/**
 * 200705
 * BOJ 16562 친구비
 * union-find
 * */

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, TOT;
int cost[10005];
int parent[10005];
int check[10005];
int ans = 0;

int findParent(int x){
    if(x==parent[x]) return x;
    return parent[x]=findParent(parent[x]);
}

bool isSameParent(int a, int b){
    return findParent(a)==findParent(b);
}

void unite(int a, int b){
    a = findParent(a);
    b = findParent(b);

    if(cost[a]<cost[b]) parent[b] = a;
    else parent[a] = b;
} 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M >> TOT;

    for(int i=1; i<=N; i++){
        cin >> cost[i];
        parent[i] = i;
    }
    
    int from, to;
    for(int i=0; i<M; i++){
        cin >> from >> to;

        if(!isSameParent(from, to))
            unite(from, to);
    }

    for(int i=1; i<=N; i++){
        int node = findParent(i);
        if(check[node]) continue;

        check[node]=true;
        ans += cost[node];
    }

    if(ans<=TOT) cout << ans;
    else cout << "Oh no";

    return 0;
}