[백준] 16562번 친구비 (Union-find) C++

1. 문제 이해

준석이의 돈 : K원

친구를 사귀려면 학생 i에게 A[i]만큼 돈을 주어야 한다.

하지만 친구의 친구는 친구다!

ex) 1의 친구가 5라면 1에게 또는 5에게만 돈을 주면 된다.

-> 그렇다면 제일 비용이 적은 친구에게 돈을 주자

그렇게 모든 사람과 가장 적은 비용으로 친구가 되는 방법을 구하라.

2. 추상화

5 3 20
10 10 20 20 30
1 3
2 4
5 4

Cost[]

10원

10원

20원

20원

30원

친구 구조 : 

1<->3 ,   2<->4  ,  5<->4 여기서 트리로 나타내야겠다 생각했다.

Fig1. 친구 구조

3. 문제 설계

모든 사람이 친구가 되려면 K(진석이가 가진 돈)원 내로 집합의 하나를 선택할수 있어야 한다.

처음 생각으로는 백트래킹으로 1->3 3에서 더 없으면  cost[1], cost[3]비교 이렇게 생각했다.

하지만 노드가 많아질 경우 최소값 찾기 + 몇개의 노드를 거쳐간지 찾기로 두번의 트래킹이 필요하다.

방법을 못찾아 검색해서 Union-find 코드를 가져와서 이해했다.

 

https://howudong.tistory.com/280

[C++] 백준/BOJ - 16562 : 친구비

해당 사이트를 참고했다.

 

풀이 코드

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

vector<vector<int>> v;
int money;
int parent[10001];
int cost[10001];

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

void merge(int x, int y) {
    int a = find(x);
    int b = find(y);
    if (a != b) {
        if (cost[a] > cost[b]) {
            parent[a] = b;
        } else {
            parent[b] = a;
        }
    }
}

int main(void) {

    int N, M, x, y;
    int out=0;
    cin >> N >> M >> money;
    for (int i = 1; i <=N; i++) {
        cin >> cost[i];
    }
    for (int i = 0; i <=N; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < M; i++) {
        cin >> x >> y;
        merge(x, y);
    }
    set<int> s;
    for(int i=1; i<=N; i++) {
        s.insert(find(i));
    }

    for(auto itr = s.begin(); itr!=s.end(); itr++) {
        out+=cost[*itr];
        money -= cost[*itr];
    }
    if(money>=0) {
        cout << out;
    } else {
        cout << "Oh no";
    }
}

4. 새로운 개념 이해

Union-Find의 모습은 결국 최상위 노드를 찾는 과정이다.

그렇다면 배열안에 값은 무조건 존재하여야 하며, Index로 배열의 값을 대체하든 해야한다.

경우의 수가 존재하는 경우, 또는 그 안에서 하나의 노드를 선택해 최고 긴 길이를 구하는 경우에 사용할수 있을 거 같다.