[BAE/<JOON> 문제풀이] 1922. 네트워크 연결

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

1922번: 네트워크 연결

스패닝 트리 문제이다.

 

이런 간선 비용을 구하는 문제는 대부분 간선 위주 연결로 해결할 수 있는 문제이다.

 

간선 비용을 정렬해두고 하나하나 연결하며 최종 값을 찾는 방식이다. 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct eg {
    int s, e, p;
};

vector<int> parent;

bool operator < (eg e1, eg e2) {
    return e1.p < e2.p;
}

bool operator > (eg e1, eg e2) {
    return e1.p < e2.p;
}

int findp(int x) {
    if (parent[x] == x) {
        return x;
    }
    else {
        return parent[x] = findp(parent[x]);
    }
}


int main()
{
    int n, m;
    cin >> n >> m;

    parent.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    vector<eg> arr;

    arr.push_back({ 0, 0, 0 });

    for (int i = 1; i <= m; i++) {
        eg imsi;
        cin >> imsi.s >> imsi.e >> imsi.p;
        arr.push_back(imsi);
    }

    sort(arr.begin(), arr.end());

    int conn = 0;
    int psum = 0;

    for (int i = 1; i <= m; i++) {
        int p1 = findp(arr[i].s);
        int p2 = findp(arr[i].e);
        if (p1 != p2) {
            parent[p2] = p1;
            psum += arr[i].p;
            if (++conn == n - 1) {
                break;
            }
        }
    }

    cout << psum << endl;
}