[백준][C++] 14621 나만 안되는 연애

www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    - 기본적인 크루스칼 알고리즘에 양쪽 노드가 다른 성별인지 확인해주는 조건만 걸어주면 된다.

        1. 노드의 성별을 저장할 배열을 생성한다.

        2. 사이클을 확인하는 부분에 다른 성별인지 확인하는 조건을 추가한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
vector<char> nodes;
vector<int> parents;
vector<pair<pair<int, int>, int> > edges;
 
 
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.second < b.second;
}
 
 
int get_parent(int a){
    if(parents[a] == a) return a;
    else return parents[a] = get_parent(parents[a]);
}
 
 
bool is_cycle(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a == b) return true;
    else return false;
}
 
 
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;
}
 
 
bool is_diff(int a, int b){
    if(nodes[a] == nodes[b]) return false;
    else return true;
}
 
 
void kruskal(){
    
    for(int i=1; i<=n; i++) parents[i] = i;
    sort(edges.begin(), edges.end(), cmp);
 
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        
        // 사이클인지 확인 && 양쪽 노드가 다른 성별인지 확인
        if(!is_cycle(edges[i].first.first, edges[i].first.second) 
        && is_diff(edges[i].first.first, edges[i].first.second)){
            union_parents(edges[i].first.first, edges[i].first.second);
            sum += edges[i].second;
        }
    }
    
    // 모두 연결되었는지 확인 
    int p = parents[1];
    for(int i=1; i<=n; i++){
        if(get_parent(i) != p){
            cout << -1 << "\n";
            return;
        }
    }
    cout << sum << "\n";
}
 
int main(void){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin >> n >> m;
    
    nodes.resize(n+1);
    parents.resize(n+1);
    
    char c;
    for(int i=1; i<=n; i++){
        cin >> nodes[i];
    }
    
    int u,v,cost;
    for(int i=0; i<m; i++){
        cin >> u >> v >> cost;
        edges.push_back({{u, v}, cost});
    }
    
    kruskal();
    
    return 0;
}

 

 

 

시행착오