백준 16562번: 친구비

Seungil Kim·2021년 11월 19일
0

PS

목록 보기
96/206

친구비

백준 16562번: 친구비

아이디어

친구끼리 Union해주는데 이 때 친구비가 제일 저렴한 애가 루트가 되도록 합친다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, M, K, cost[10000];

typedef struct _DisjSet {
    int parent[1000001] = {0,};
    
    void init(int n) {
        for (int i = 0; i < n+1; i++) {
            parent[i] = i;
        }
    }
    
    int find(int n) {
        if (parent[n] == n) return n;
        return parent[n] = find(parent[n]);
    }
    
    void Union(int n1, int n2) {
        n1 = find(n1);
        n2 = find(n2);
        if (n1 == n2) return;
        if (cost[n1] < cost[n2]) parent[n2] = n1;
        else parent[n1] = n2;
    }
    
} DisjSet;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M >> K;

    DisjSet d;
    d.init(N);
    
    for (int i = 0; i < N; i++) {
        cin >> cost[i];
    }
     
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        d.Union(a-1, b-1);
    }
    
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (d.find(N) == d.find(i)) continue;
        ans += cost[d.find(i)];
        d.Union(N, i);            
    }
    if (ans <= K) cout << ans;
    else cout << "Oh no";
    return 0;
}

여담

맨 처음에는 cost[루트 인덱스]에 각 집합의 최소 친구비가 들어가도록 짰는데 잘 안됐다. 왜안됐지? 솔직히 아직도 잘 모르겠다.

for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    d.Union(a-1, b-1);
    cost[d.find(a-1)] = min(cost[d.find(a-1)], min(cost[a-1], cost[b-1]));
}

이렇게 했는데 어딘가 빼먹는게 있었나봄.. 유니온 파인드에서는 최대한 루트만 참조하도록 짜야겠다.

profile
블로그 옮겼어용 https://ks1ksi.io/

4개의 댓글

comment-user-thumbnail
2021년 11월 20일

친구비 얼마인가요 계좌 불러주시죠

1개의 답글
comment-user-thumbnail
2021년 11월 21일

ㅈㅅ;; 저번달 친구비 못 보냄 봐주셈

1개의 답글