[백준][C++] 1414 불우이웃돕기

www.acmicpc.net/problem/1414

1414번: 불우이웃돕기

 

 

 

알고리즘 종류

MST

크루스칼

 

 

 

사고 과정

입력된 모든 랜선의 길이를 저장합니다. 그리고 크루스칼 알고리즘으로 MST를 만들면 연결된 길이를 빼줍니다. 그리고 모든 컴퓨터가 연결되었는지 확인해야 합니다. 모든 컴퓨터가 연결되어 있는지 확인할 수 있는 방법은 무엇일까요?

 

A노드와 B노드가 연결되어 있는지는 parents 배열에 저장해두었습니다. 그렇다면, 이 배열을 for문으로 순환하면서 부모가 모두 동일하다면 모든 노드가 연결되어 있는 것 입니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
int total=0;
 
int parents[101];
vector<pair<int, pair<int, int> > > edges;
 
bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b){
    return a.first < b.first;
}
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);
}
 
void union_parents(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a > b) parents[a] = b;
    else parents[b] = a;
}
 
void solution(){
    
    for(int i=1; i<=n; i++) parents[i] = i;
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i=0; i<edges.size(); i++){
        int node1 = edges[i].second.first;
        int node2 = edges[i].second.second;
        int cost = edges[i].first;
        
        if(get_parent(node1) != get_parent(node2)){
            union_parents(node1, node2);
            total -= cost;
        }
    }
    
    int p = get_parent(1);
    for(int i=2; i<=n; i++){
        if(get_parent(i) != p){
            cout << -1 << endl;
            return;
        }
    }
    cout << total << endl;
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
 
    char c;
    int cost;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> c;
            
            if(c >= 'a' && c <= 'z'){
                cost = c - 'a' + 1;
                edges.push_back({cost, {i, j}});
                total += cost;
            }
            else if(c >= 'A' && c <= 'Z'){
                cost = c - 'A' + 27;
                edges.push_back({cost, {i, j}});
                total += cost;
            }
        }
    }
 
    solution();
}

 

 

 

시행착오