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

14621. 나만 안되는 연애
문제 풀이

14621번: 나만 안되는 연애

 

최소 스패닝 문제에서 서로 다른 타입의 노드만 연결할 수 있다는 조건 하나를 추가한 문제!

어렵지 않게 풀 수 있었다.

 

알고리즘 설계

1. W인지 아닌지 판별하는 bool형 배열을 만들고 입력받는다.
2. 간선을 입력받을 때, 서로 다른 노드라면 간선 배열에 저장해준다.
3. 간선들을 가중치 기준으로 오름차순으로 정렬한다.
4. 사이클이 생기지 않게 크루스칼 알고리즘으로 최소 스패닝 트리의 비용을 구한다!
5. 정점의 수 - 1개의 간선으로 구성되지 않았다면, -1을 출력한다.

 

코드

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ulli;

// 간선 구조체
struct Edge
{
    int a, b, w;

    bool operator < (const Edge& e) const
    {
        return w < e.w;
    }
};

int parents[1001];
bool isWoman[1001];
vector<Edge> edges;

// union-find
int find(int v)
{
    vector<int> memo;

    while (parents[v] != v)
    {
        v = parents[v];
        memo.push_back(v);
    }

    for (int i : memo) parents[i] = v;

    return v;
}
bool uni(int a, int b)
{
    int fa = find(a), fb = find(b);

    if (fa != fb)
    {
        parents[fa] = fb;
        return true;
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    int vCnt, lCnt, result = 0;
    cin >> vCnt >> lCnt;

    // 각 노드의 위치를 입력 받는다
    for (int i = 1; i <= vCnt; i++)
    {
        char c;
        cin >> c;

        isWoman[i] = (c == 'W');
        parents[i] = i;
    }

    for (int i = 0; i < lCnt; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;

        if (isWoman[a] != isWoman[b])
        {
            edges.push_back({ a,b,w });
        }
    }


    // 크루스칼
    sort(edges.begin(), edges.end());

    for (int i = 0; i < edges.size(); i++)
    {
        if (uni(edges[i].a, edges[i].b))
        {
            vCnt--;
            result += edges[i].w;
        }
    }

    if (vCnt == 1)
        cout << result;
    else                 // 스패닝 트리가 만들어지지 않았을 때
        cout << -1;
}

최소 스패닝 트리 + 처음 보는 조건이 들어있는 문제라 재미있었다!