[Baekjoon - 1414] 불우이웃돕기

난이도: Gold III

 

태그

• Minimum Spanning Tree
• Disjoint-Set Union

 

풀이

1. 모든 컴퓨터가 연결되어있는 상태를 만들 수 있을까?

만약 초기 상태부터 연결되지 않은 쌍이 존재했다면, 간선을 더 없애도 그 쌍을 연결시킬 수는 없으므로 불가능합니다.

반대로, 모든 컴퓨터가 연결되어있었다면, 간선을 0개 자르는 방식으로 모든 컴퓨터를 연결시킨 상태를 만들 수 있기 때문에, 가능합니다.

 

2. 기부할 수 있는 랜선의 최댓값은?

모든 컴퓨터를 연결시키면서 기부할 수 있는 랜선을 최대화한다는 건,

연결성을 유지시키되 남기는 랜선을 최소화한다는 것을 의미합니다.

이는 결국 Minimum Spanning Tree 문제이기 때문에, (총 랜선 길이) - (MST에 남는 간선 길이)를 출력해주면 됩니다.

 

3. 코드

inline int f(char ch){
    if ('a' <= ch && ch <= 'z'){ return ch-96; }
    if ('A' <= ch && ch <= 'Z'){ return ch-64+26; }
}
 
int par[60];
int fnd(int a){ return par[a] = (par[a] == a ? a : fnd(par[a])); }
void uni(int a, int b){ par[fnd(b)] = fnd(a); }
 
void Main(){
    vector<pi3> edg;
    int n; cin >> n; int sum = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            char ch; cin >> ch;
            if (ch != '0'){ edg.push_back({ {i, j}, f(ch) }); sum += f(ch); }
        }
    }
    for (int i = 1; i <= n; i++){ par[i] = i; }
    sort(all(edg), [](pi3 a, pi3 b){ return a.sc < b.sc; });
    int ans = 0, cnt = 0;
    for (pi3 p : edg){
        int v = p.fr.fr, w = p.fr.sc; int x = p.sc;
        if (fnd(v) != fnd(w)){ ans += x; cnt += 1; uni(v, w); }
    }
    if (cnt != n-1){ cout << -1; } else{ cout << sum-ans; }
}