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

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

 

 

이 문제는 친구들의 관계에 대한 그래프가 주어지고 각 친구에 대한 친구비용이 주어졌을때

N명의 학생들이 모두 친구가 되기 위해서 최소 비용을 출력하는 문제이다.

 

1. 친구들의 관계가 주어진다. -> 그래프 형태로 표현 가능하다.

2. 최소비용을 출력하라 -> 친구 관계에서 루트 노드를 비용이 가장 작은 친구로 두어야한다.

 

유니온 파인드 알고리즘을 사용하여 각 그래프에서 루트 부분을 가장 작은 비용이 드는 친구를 선택하여 만들어

 

set에 부모노드를 넣어 합하면 최소비용이 만들어진다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N, M, K;
int friendCost[10001];
int unf[10001];

int Find(int a) {
    if(a == unf[a]) return a;
    return unf[a] = Find(unf[a]);		// 좌표 압축
}

void Union(int a, int b) {		// 비용이 가장 적은 친구를 루트로 만듬
    a = Find(a);
    b = Find(b);

    if(friendCost[a] > friendCost[b]) {
        unf[a] = b;
    }
    else unf[b] = a;
}

bool isUnion(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a == b) return true;
    else return false;
}

void Init() {
    for(int i = 1; i <= N; i++) {
        unf[i] = i;			// 초기에 자기 자신을 루트로 설정
    }
}

void solve() {
    set<int> st;

    for(int i = 1; i <= N; i++) {
        st.insert(Find(unf[i]));
    }

    int cost = 0;

    for(auto it : st) {
        cost += friendCost[it];
    }

    if(cost <= K) {
        cout << cost;
    }
    else cout << "Oh no";
}

void input() {
    cin >> N >> M >> K;

    Init();

    for(int i = 1; i <= N; i++) {
        cin >> friendCost[i];
    }

    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        Union(a, b);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();

    return 0;
}