[알고리즘 풀이 분석] BOJ 16562 친구비

오늘 풀어본 두번째 문제는 BOJ 16562 친구비 이다! 레벨은 골드 3 문제이고 유니온 파인드를 이용해서 풀었다. 로직이 바로 생각이 났는데 꼼꼼하게 생각하지 않아서 괜히 시간이 오래 걸렸다,, 문제를 똑바로 세세하게 확인해서 시작하는 연습이 부족한 것 같다ㅜ

BOJ 16562 친구비

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입출력

나의 풀이

로직 자체는 굉장히 단순하다. 관계가 있는 친구들끼리 하나의 집합으로 묶고 집합별로 가장 비용이 저렴한 친구만 골라서 비용의 합을 구하면 되는 문제이다.

union-find 알고리즘을 사용할 수 있는데 굉장히 오랜만에 써서 너무 대충 생각했다... (조건좀.. 딱딱 읽고.. 정리 하고.. 진정하고.. 풀어라...🤦🏻‍♀️)

먼저 입력되는 v-w 에 따라서 둘중에 비용이 더 적은 친구로 parents[i] 를 채워준다. 만약 1(cost=10) - 3(cost=30) 이 친구관계라면 parents[3] = 1 이 된다.

이후 3-5(cost=50) 이 친구관계라면 이제 3을 사귀는데 있어서 필요한 비용을 1을 사귀는데 필요한 비용, 10과 동일하므로 cost[1] = 10, cost[5] = 50 을 비교하여 parents[5] = 1 이 된다.

다음과 같은 예시를 보자.

5 4 100
1 2 3 4 5
1 5
2 4
4 3
5 4

위 입력대로라면 parents 배열은 다음과 같이 변화한다.

5 4 가 입력으로 들어왔을 때 4-5의 cost만을 비교한 뒤 parents[5] 를 4로 바꿔준다면 결과적으로 집합은 (1-5) 와 (2-3-4) 두가지가 생긴다.

이러한 경우의 발생을 방지하기 위해 cost를 비교하고 부모를 바꿔줄 때는 항상 최종 부모를 찾아서 비교해야 한다.

즉, parents[4] = 2 이지만 parents[2] = 2 까지 올라간 뒤 cost[2] 와 cost[5]를 비교해야 올바르게 집합을 형성할 수 있다.

이 부분만 주의한다면 큰 어려움 없이 해결할 수 있을 것이다!

코드

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

// BOJ 16562 친구비, 유니온파인드 사용, 골드 3
using namespace std;

vector<int> cost;
vector<int> parent;

// 최종 부모 친구를 찾아서
int getParent(int x){
    if(parent[x] == x) return x; // 최종 부모이면 반환
    else return getParent(parent[x]);
}
//두 친구를 같은 집합으로
void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(cost[a] <= cost[b]) parent[b] = a;
    else parent[a] = b;
}

int getMinCost(vector<pair<int, int>> relation){
    int total = 0;
    vector<int> finalParents;

    // 친구들 묶어주기
    for (int i = 0; i < relation.size(); ++i) {
        unionParent(relation[i].first, relation[i].second);
    }

    // 최종 부모만 골라서
    for (int i = 1; i < parent.size(); ++i) {
        finalParents.push_back(getParent(i));
    }

    // 최종 부모 배열 중복 제거
    sort(finalParents.begin(), finalParents.end());
    finalParents.erase(unique(finalParents.begin(), finalParents.end()), finalParents.end());

    // 최소 비용 구하기
    for (int i = 0; i < finalParents.size(); ++i) {
        total += cost[finalParents[i]];
    }

    return total;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, k;
    cin>>N>>M>>k;

    cost.assign(N+1, 0);
    parent.assign(N+1, 0);
    vector<pair<int, int>> relation(M, make_pair(0,0));

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

    int totalCost = 0;
    if (M==0){  // 생성되어 있는 관계가 없을 때
        for (int i = 1; i <= N ; ++i) {
            totalCost += cost[i];
        }
    }else{
        for (int i = 0; i < M; ++i) {
            cin>>relation[i].first>>relation[i].second;
        }
        totalCost = getMinCost(relation);
    }

    if (totalCost > k){  // 준석이의 돈보다 많이 필요하면
        cout<<"Oh no";
    }else{
        cout<<totalCost;
    }

    return 0;
}