[백준] 14621번 나만 안되는 연애(c++)

문제 및 입출력

문제 접근

MST(최소 신장 트리)를 이용해서 문제를 풀었다.
문제를 구현할 때는 KRUSKAL 알고리즘을 사용해서 풀었다.
priority_queue를 간선에 넣어서, 간선들을 하나씩 빼고 성별이 같은 대학교 인지 체크를 하고, 만약 같은 성별 대학교라면, 패스를 해주고, 해당 간선을 추가하면 cycle여부를 체크하고 cycle이 생긴다면 패스해주었다.
cycle를 체크할 때는 union-find를 사용하여 구현했다.

코드 구현(c++)

#include <iostream>
#include <queue>
#define MAX 1001

using namespace std;

int parent[MAX];
bool college[MAX]; // 남자 true, 여자 false
int N, M;
int cnt = 0;
int res = 0;

priority_queue<pair<int, pair<int,int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int,int> > > >pq;

int Find(int n){
    if(parent[n] == n) return n;
    else return Find(parent[n]);
}
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    
    parent[y] = x;

}
void init(){
    for(int i = 1 ; i <= N ; i++){
        parent[i] = i;
    }
}

int bfs(){
    // 먼저 priority_queue에서 하나를 꺼내서 간선과 연결되어있는 노드가 다른 성별인지 체크
    // 다른 성별이라면, parent가 같은지 체크
    while(!pq.empty()){
        int num = pq.top().first; int n1 = pq.top().second.first; int n2 = pq.top().second.second;
        pq.pop();
        if(college[n1] == college[n2]) continue;
        if(Find(n1) == Find(n2)) continue;
        if(cnt == N - 1) return res;
        //연결하기
        Union(n1,n2);
        res += num;
        cnt++;
    }
    if(cnt == N - 1) return res;
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> N >> M;
    init();
    char s;
    for(int i = 0 ; i < N ; i++){
        cin >> s;
        if(s == 'M') college[i+1] = true;
        else college[i+1] = false;
    }
    int n1, n2, num;
    for(int i = 0 ; i < M ; i++){
        cin >> n1 >> n2 >> num;
        pq.push(make_pair(num, make_pair(n1, n2)));
    }
    cout << bfs() << "\n";
}