백준(BOJ) 14621 나만 안되는 연애 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/14621

14621번: 나만 안되는 연애

문제 풀이에 이용된 알고리즘: 크루스칼 알고리즘

 

주어진 그래프에서, 노드들을 연결하는 최단 거리 트리를 생성하는 문제이다. 즉, 최소 신장 트리 문제이며 크루스칼 알고리즘으로 간단히 풀 수 있다.

 

단, 간선을 입력 받을 때 "남초<->남초" 혹은 "여초<->여초"를 연결하는 간선은 애초에 크루스칼 알고리즘의 대상이 되는 간선 그룹에 포함시키지 않는다는 점이 중요하다.

 

최초 모든 대학을 연결하는 경로가 있다라는 조건이 있지 않고, 모든 대학을 연결하는 경로를 찾지 못하는 경우 -1을 출력하라고 했기 때문에, 크루스칼 알고리즘이 끝났을 때 바로 신장 트리의 길이를 출력하는 것이 아니라, 신장 트리를 구성하는 간선이 "노드의 개수 - 1"인지 확인하여야 한다.

 

이 조건을 만족하지 못하면 -1을 출력하도록 한다.

 

/* BOJ 나만 안되는 연애 */
/* MST - 크루스칼 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, m, p[1001];
char school_types[1001];
vector<pair<pair<int, int>, int>> edges;
 
// find
int find_parent(int x)
{
    if (p[x] == x)
        return x;
    
    return p[x] = find_parent(p[x]);
}
 
// union
void union_parent(int a, int b)
{
    a = find_parent(a);
    b = find_parent(b);
 
    if (a < b)
        p[a] = b;
    else
        p[b] = a;
}
 
bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
    return p1.second < p2.second;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i; // 부모 배열 초기화
        cin >> school_types[i];
    }
 
    for (int i = 0; i < m; i++)
    {
        int u, v, d;
        cin >> u >> v >> d; // u <-> v는 d만큼 떨어짐
 
        if (school_types[u] != school_types[v]) // 남초<->남초 또는 여초<->여초가 아닌 경우
            edges.push_back({ {u, v}, d }); // 유의미한 간선이므로 간선그룹에 포함
    }
 
    sort(edges.begin(), edges.end(), cmp); // 간선들의 비용 기준 오름차순 정렬
    
    int ans = 0, cnt = 0;
    for (auto edge : edges)
    {
        int u = edge.first.first;
        int v = edge.first.second;
        int d = edge.second;
 
        if (find_parent(u) != find_parent(v))
        {
            // u와 v가 다른 집합에 속한다면, 즉 싸이클을 발생시키지 않는다면
            union_parent(u, v);
            ans += d;
            if (++cnt == n - 1) // 모든 대학들을 다 갈 수 있기 위해서는 (노드수-1)의 간선이 필요
            {
                cout << ans << endl;
                return 0;
            }
        }
    }
    cout << -1 << endl; // 모든 대학을 연결하는 MST 찾지 못하면 -1 출력
 
    return 0;
}