백준 16562: 친구비(c++, 분리 집합 & 유니온 파인드)

사용 언어	티어	시간 제한	메모리 제한
c++		2초	512MB

 

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

16562번: 친구비

 

#0 문제

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!
학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.
준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!
위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

 

#1 입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.
두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)
다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.

 

#2 접근

• 분리 집합을 이용하는 문제이다. 친구들 끼리 연결되어있으면 그 집합에서 비용이 가장 작은 것이 대표 비용이 될 것이다.
• 집합의 대표 비용들을 합쳐서 k보다 크면 돈이 부족할 것이고 k이하이면 그것이 최소비용일것이다.

 

#3 풀이

• 기본적인 disjoint set 코드를 만들어준다. Find와 Union을 구현해준다.
• Union을 구현할 때는 작은 번호가 부모가 되도록 해준다.
  • Find로 찾은 번호는 항상 그 집합의 가장 작은 번호가 될 것이다.
  • 두 집합을 합칠 때, 작은 번호에 해당하는 cost의 최솟값을 갱신해준다.
  • 예를 들어 Find로 찾은 u가 3, v가 1일 때(각각 집합의 대표값) u > v 이므로 u의 부모는 v가 된다.
  • 이 경우 집합의 대표값은 v가 된다. 그렇다면 대표값의 최솟값을 갱신해주어야 한다.
  • v의 최솟값은 u 집합의 최솟값과 v 집합의 최솟값중에 더 작은 것이 될 것이다.
  • u < v일 경우도 동일하게 진행해주면 된다.
• 모든 v, w에 대해 Union을 진행해준 후 최소 비용을 구한다.
• 이때 집합의 방문 여부를 체크할 필요가 있다. 
  • Find를 통해서 집합의 대표값을 찾고, 아직 방문하지 않은 집합일 경우에만 최소비용을 더해준다.
• 최소 비용이 k 보다 클 경우 "Oh no"를 출력하고 아닐 경우 최소 비용을 출력해준다.

 

#4 코드

/*
16562 친구비
유니온 파인드
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>



using namespace std;



int n, m, k;
int friend_cost[10001];
int dsu[10001];
int visited[10001];


int Min(int a, int b) { return a < b ? a : b; }


int Find(int x) {
    return x == dsu[x] ? x : dsu[x] = Find(dsu[x]);
}


void Union(int u, int v) {
    u = Find(u);
    v = Find(v);

    if (u > v) {
        dsu[u] = v;
        friend_cost[v] = Min(friend_cost[v], friend_cost[u]);
        
    } else if (u < v) {
        dsu[v] = u;
        friend_cost[u] = Min(friend_cost[v], friend_cost[u]);
    }
}



int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> k;

    iota(dsu + 1, dsu + n + 1, 1);


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

    int v, w;

    for (int i = 0; i < m; ++i) {
        cin >> v >> w;
        Union(v, w);
    }

    int cost = 0;

    for (int i = 1; i <= n; ++i) {
        int temp = Find(i);
        if (!visited[temp]) {
            visited[temp] = 1;
            cost += friend_cost[temp];
        }
    }

    if (cost > k) {
        cout << "Oh no";
    } else cout << cost;

    return 0;
}