[백준][C++] 1922 네트워크 연결

1922. 네트워크 연결
문제 풀이

1922번: 네트워크 연결

 

단순 최소 스패닝 트리를 구하는 문제!

 

위 문제처럼 크루스칼이나 프림을 사용하면 된다고 생각해, 좀 더 쓰기 번거롭지 않은 크루스칼 + 메모이제이션을 이용했다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int parents[1001];

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

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

// 최상위 부모 찾기 
int find(int v)
{
    vector<int> vec;

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

    // 메모이제이션 
    for (int i : vec)
    {
        parents[i] = v;
    }

    return v;
}

int main()
{
    int vCnt, lCnt;
    long long int result = 0;
    vector<Edge> edges;

    cin >> vCnt >> lCnt;

    for (int i = 0; i <= vCnt; i++)
        parents[i] = i;

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

        edges.push_back({ a,b,w });
    }

    // 가중치 기준 오름차순 정렬 
    sort(edges.begin(), edges.end());

    for (int i = 0; i < edges.size(); i++)
    {
        int fa = find(edges[i].a), fb = find(edges[i].b);

        // 사이클이 생기지 않는다면
        // 간선 선택  
        if (fa != fb)
        {
            result += edges[i].w;
            parents[fa] = fb;
        }
    }

    cout << result;
}

단순하게 최소 스패닝 트리 구현 문제였지만, 다음에는 최소 스패닝 트리를 이용한 응용 문제를 풀어보고 싶다!!!!