BOJ 16562 - 친구비

www.acmicpc.net/problem/16562

16562번: 친구비

 

이 문제는, 유니온 파인드를 써서 푸는 문제이다.

문제에서 주어진 "친구의 친구는 친구다" 라는 문구로 미뤄 봤을때,

같은 집합에 소속된 노드라면, 따로 비용계산을 하지 않아도 된다는 의미가 되기때문에, 유니온 파인드를 써서 동일 집합인지 아닌지 판별하면 되는것임을 의미한다.

그리고 최소 비용으로 전체와 친구가 되야 하므로, 친구비가 더 적게 드는 쪽을 부모 노드로 선택해서 집합으로 묶는다.

 

- c++

#include <bits/stdc++.h>
 
#define MAX 10001
 
using namespace std;
 
int N, M, K, answer;
int money[MAX], parent[MAX];
 
int _find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = _find(parent[x]);
}
 
void _union(int x, int y) {
    x = _find(x);
    y = _find(y);
    
    if (x == y) return;
    
    if (money[x] < money[y]) parent[y] = x; // 친구비 더 적은 놈이 부모 
    else parent[x] = y;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
            
    cin >> N >> M >> K;
    
    for (int i = 1; i <= N; ++i) cin >> money[i];
    
    for (int i = 0; i <= N; ++i) parent[i] = i;
 
    while(M--) {
        int v, w;
        cin >> v >> w;
        _union(v, w);
    } 
    
    for (int i = 1; i <= N; ++i) 
        if (parent[i] == i) // 다른 집합이면 친구비 내야 
            answer += money[i];
    
    if (K < answer) cout << "Oh no";
    else cout << answer;
    
    return 0;
}

 

 

 

 

- 참고

ssungkang.tistory.com/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find

[Algorithm] 유니온 파인드(Union - Find)