[백준] 16562번 친구비

 

[적용한 알고리즘]

유니온 파인드

 

[아이디어]

유니온 파인드에서 parent를 먹여주는 방식은 상관없었는데, 

일정한 규칙을 부여해줘서 parent가 될 조건을 정해주면 

항상 root 노드에는 친구비들 중 최소값이 저장되어 있을 것이다.

(우선선위 큐 같은 느낌인가?)

 

[생각의 흐름 / 절차] 

아이디어를 제외하면 유니온 파인드이다.

마지막 : 전부 친구가 될 수 없는 조건은 돈이 초과되는 상황밖에 없으니 조건문으로 분기 나눠주면 됨.

 

 

[교훈]

유니온 파인드에서 트리를 만들어가는데

parent를 정해주는데 규칙을 적용하면 (집합) + (또 다른 규칙)을 포함한 트리를 

나타내준다고 생각할 수도 있겠다. 

 

<코드>

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

int parent[10001];
int a[10001];

int find(int x){
    if (parent[x] < 0) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y){
    x = find(x);
    y = find(y);

    if (x == y) return;
    //친구비가 더 작은 애가 parent가 될 수 있도록 한다.
    if (a[x] < a[y]) parent[y] = x;
    else parent[x] = y;
}

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    fill(parent, parent + n + 1, -1);

    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }

    while (m--){
        int x, y;
        scanf("%d %d", &x, &y);
        merge(x, y);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++){
        if (parent[i] == -1){
            ans += a[i];
        }
    }

    if (k < ans) printf("Oh no\n");
    else printf("%d\n", ans);

    return 0;
}