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

https://www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

 

 

[ 문제풀이 ]

 

1. 여초와 남초를 저장할 univ 배열을 만들고, 각자의 부모를 저장할 vect 배열을 만듭니다.

 

2. 간선을 입력받고, 비용을 기준으로 오름차순으로 정렬합니다.

 

3. Union-Find를 이용하여 각각의 노드가 부모가 서로 다르고, 대학도 서로 다르다면 합쳐줍니다.

 

4. 이 때, ans에 비용을 더해주고, cnt++를 해줍니다.

 

5. cnt가 N-1과 같다면 ans를 출력하고, 그렇지 않다면 -1을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int u;
    int v;
    int d;
};
 
bool cmp(node left, node right)
{
    return left.d < right.d;
}
 
int N, M;
char univ[1001];
int vect[1001];
node arr[10000];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        getchar();
        scanf("%c", &univ[i]);
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d %d", &arr[i].u, &arr[i].v, &arr[i].d);
    }
 
    sort(arr, arr + M, cmp);
 
    int ans = 0;
    int cnt = 0;
 
    for (int i = 0; i < M; i++) {
        const int u = arr[i].u;
        const int v = arr[i].v;
        const int d = arr[i].d;
 
        if (Find(u) != Find(v) && univ[u] != univ[v]) {
            Union(u, v);
            ans += d;
            cnt++;
        }
    }
 
    if (cnt == N - 1) {
        printf("%d", ans);
        return 0;
    }
 
    printf("-1");
}