[BOJ] 백준 16562 친구비 c++ (유니온 파인드)

문제 출처 :https://www.acmicpc.net/problem/16562 

16562번: 친구비

---

풀이

불쌍한 준석이,,, 우선 완전탐색으로 생각했으나 유니온 파인드로 해결해야하는 문제임을 깨달았다.

유니온 파인드는 아래 패턴을 기억해야 할 것 같다.

 

1. 같은 집합으로 묶어주는 함수(unionParent)

root를 찾아주는 함수(getParent)로 가져온 후 서로의 부모를 지정해준다.

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    // 부모 우선순위에 따라 작성
    if(a != b){
        if(pay[a] > pay[b]) parent[a] = b;
        else parent[b] = a;
    }
}

 

2. root를 찾아주는 함수(getParent)

parent가 자신이라면 본인이 root라는 의미이므로 리턴한다.

parent는 재귀적으로 구해 최상단의 root를 찾는다.

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

 

이렇게 서로 연결된 집합을 설정해준 후

준석이(0번 idx)와 root가 다른 경우 친구비를 정답에 더해주고, 같은 집합으로 묶어주면 된다.

이렇게 가진 돈보다 친구비가 많으면 Oh no, 같거나 작으면 출력하면 된다.

---

코드

#include <bits/stdc++.h>

using namespace std;

int ans;
int parent[10000+1];
int pay[10000+1];

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

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b){
        if(pay[a] > pay[b]) parent[a] = b;
        else parent[b] = a;
    }
}

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

    int N, M, k;
    cin >> N >> M >> k;

    pay[0] = INT_MAX;
    for(int i = 1; i <= N; i++){
        cin >> pay[i];
        parent[i] = i;
    }

    for(int i = 0; i < M; i++){
        int v, w;
        cin >> v >> w;
        unionParent(v, w);
    }

    for(int i = 1; i <= N; i++){
        int root = getParent(i);
        if(root != getParent(0)){
            ans += pay[root];
            unionParent(0, i);
        }
    }
    if(k >= ans)
        cout << ans;
    else cout << "Oh no";
	return 0;
}