[ BOJ 백준 16562번 - 친구비 ] 해설 및 코드

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

 

목적

친구의 친구도 친구라는 규칙(?)에 따라 모든 학생과 친구가 되기 위해 필요한 최소 비용을 구하자.

 

접근법

1. 분리집합을 이용한다. 다만, 비용이 적은 학생을 루트 노드로 하는 집합을 형성하자.

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
const int LEN = 1e4 + 1;
int a[LEN], cost[LEN];
 
int root(int i) {
    while (i != a[i])a[i] = a[a[i]], i = a[i];
    return i;
}
 
void connect(int i, int j) {
    i = root(i), j = root(j);
    if (i == j)return;
 
    if (cost[i] < cost[j]) a[j] = i;
    else a[i] = j;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, k; cin >> n >> m >> k;
    f(i, 1, n) {
        cin >> cost[i];
        a[i] = i;
    }
    while (m--) {
        int v, w; cin >> v >> w;
        connect(v, w);
    }
 
    int ans = 0;
    bool chk[LEN]{};
    f(i, 1, n) {
        int tmp = root(i);
        if (chk[tmp])continue;
        chk[tmp] = true;
        ans += cost[tmp];
        if (ans > k) {
            ans = -1;
            break;
        }
    }
    if (ans == -1)cout << "Oh no";
    else cout << ans;
    cout << '\n';
 
    return 0;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.