[C++] 백준/BOJ - 16562 : 친구비

---

문제 이해 단계

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

16562번: 친구비

N명이 학생이 있고 그 학생들 사이에 M개의 친구 관계가 존재한다.

그리고 각각의 학생마다 친구비가 존재하는데,
친구 관계인 친구였다면 그중 하나에게만 지불하면 된다.

해당 조건으로 K원을 가지고 있을 때,
N명 학생과 모두 친구를 맺을 수 있는 최소 비용을 구하시오.

만약 구할 수 없으면 "Oh no"를 출력한다.

 

 

---

문제 접근 단계

N명의 학생이 있고 그 친구들 사이에 관계가 존재한다.
이를 다르게 보면 정점과 간선의 관계로 볼 수 있다.

중요한 것은 N명마다 각각의 비용을 가지고 있고,
우리는 최소 비용으로 친구를 맺어야 한다는 것.

상식적으로 생각해 볼 때, 가장 적은 비용을 쓰기 위해서는
각각의 친구 관계에서 최소한의 비용을 가진 사람을 선택해야 한다.

그렇게 하면 그 비용만으로도 그 사람과
친구관계인 사람을 모두 얻을 수 있기 때문이다.

즉, 이 문제의 핵심은 2가지 인 것 같다.

1. 친구 관계인 그룹(집합)끼리 잘 묶을 수 있는가?
2. 각 그룹 중에 가장 낮은 비용을 가진 사람을 뽑아낼 수 있는가?

 

---

집합끼리 잘 묶을 수 있는가?

이 문제는 각 친구들을 정점으로 보고,
친구 관계를 간선으로 볼 때 어떻게 할 것인가가 고민이다.

여기서 나는 같은 집합이라면 최상위 부모가 같으면 되지 않을까?
해서 유니온-파인드 방식을 사용하기로 했다.

유니온 파인드 방식을 사용해서 같은 그룹으로 묶는다.
여기서 최상위 부모는 비용이 제일 작은 친구로 설정한다.

그렇게 하면 나중에 뽑아내기도 편해지기 때문이다.

이렇게 되면 2번 문제인
"각 그룹 중에 가장 낮은 비용을 가진 사람을 뽑아낼 수 있는가?" 에 대한 고민도 해결된다.

이제 이를 문제 구현 단계에서 코드로 구현해 보자.

 

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


int parent[10001];
int cost[10001];

// 최상위 부모를 찾는 파인드 함수
int find(int x){
    if(parent[x] == x) return x;

    return parent[x] = find(parent[x]);
}

// 두 그룹을 합치는 유니온 함수
void merge_parent(int a, int b){
    a = find(a);
    b = find(b);
    if(a != b){
        // 비용이 낮은 것을 부모로 설정
        if(cost[a] > cost[b]) parent[a] = b;
        else parent[b] = a;
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int N,M,k;
    cin >> N >> M >> k;

    // 초기화 = 자기 자신을 부모로 설정
    for(int i = 0; i <= 10000; i++) parent[i] = i; 
    for(int i = 1; i <= N; i++) cin >> cost[i];
    for(int i = 0; i < M; i++){
        int v,w;
        cin >> v >> w;
        merge_parent(v,w);
    }
    unordered_set<int> s;

    // 집합에 각 친구의 최상위 부모를 담음(중복 제거)
    for(int i = 1; i <= N; i++){
        s.insert(find(i));
    }
    int ans = 0;

    // 중복이 제거된후 그 비용을 담음
    for(auto it : s){
        ans += cost[it];
        k -= cost[it];
    }
    // k원이 0이상이라면 성공
    if(k >= 0) cout << ans;
    else cout << "Oh no";

}

유니온 파인드 함수를 구현하고, 답을 구하는 전체 코드이다.

find부분인 find(int x) 부분은 일반적인 유니온-파인드의 find부분이다.

union부분인 merge_parent(int a, int b)는 두 그룹의 최상위 부모가 다를 시 합치는데,

가격이 낮은 것이 최상위 부모가 되도록 설정하였다.

그리고 연산이 끝나면 각 친구들을 모두 find()에 넣어 최상위 부모를 호출하도록 한다.
그리고 이를 set에 넣어 가장 비용이 낮은 친구를 호출하게 한다.

set에 넣었으므로 중복이 제거되고 각 그룹에 비용이 적은 친구만이 남게 된다.
그리고 이를 계산에 사용한다.

설명은 여기까지이다.

 

 

---

시행착오

유니온-파인드에 그렇게 당해놓고 이번에 또 당하니까 너무 짜증 난다.

자괴감이 너무 든다. 언제쯤 익숙해질까..

처음엔 그리디로 풀다가 시간초과가 떴다.
그다음엔 머리가 멍해져서 아 유니온 파인드.. 근데 어떻게 하더라... 자신이 너무 없어졌다.

좀 제대로 해야겠다.. 제발

생활비..

https://toss.me/howudong

howudong님에게 보내주세요