BOJ(백준) 16562 - 친구비

---

아이디어

마찬가지로 분리집합에서 시작해서 합집합해가는 과정의 문제이다. 주어지는 N개의 노드와 자기자신이라는 1개의 노드가 더있다고 보았다. 자기자신을 0번노드라 하고 문제에서 주어지는 노드를 1~N번 노드라 할 때, 0번노드와 모든 노드가 하나의 집합이 되어야 하며, 합집합(merge) 연산을 할 때마다 비용이 발생한다. 그 비용이 k를 넘으면 Oh no를 출력한다.

---

점검해볼 사항

- 합집합연산을 할 때, W배열 사용하여 발생하는 비용 계산

---

시간복잡도

O(N + M) : M개의 친구관계마다 merge연산(+find연산) + N개 노드와 merge연산(+find연산)

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/16562.cpp 

#include<iostream>
#include<vector>
#define INF 1987654321
using namespace std;
vector<int> p, w;
int find(int idx) {
    if (p[idx] < 0) return idx;
    return p[idx] = find(p[idx]);
}
bool merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (w[a] < w[b]) p[b] = a;
    else p[a] = b;
    return true;
}
int main() {
    int N, M, k, ans = 0;
    scanf("%d%d%d", &N, &M, &k);
    p.resize(N + 1, -1);
    w.resize(N + 1, INF);
 
    for (int i = 1; i <= N; i++) scanf("%d", &w[i]);
    for (int i = 1, a, b; i <= M; i++) {
        scanf("%d%d", &a, &b);
        merge(a, b);
    }
    for (int i = 1; i <= N; i++) {
        if (find(0) != find(i)) {
            ans += w[find(i)];
            merge(0, i);
        }
    }
    if (ans <= k) printf("%d\n", ans);
    else printf("Oh no\n");
    return 0;
}