네트워크 연결

코드

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

int N,M,ans;
int parent[1002]; // 1~1000 사용
int findParent(int x){
    if(x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}
void unionParent(int a, int b){
    a = findParent(a);
    b = findParent(b);
    if(a<b) parent[b] = a;
    else parent[a] = b;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N;
    cin >> M;
    vector<pair<int,pair<int,int>>> edges;
    for(int i=0;i<M;i++)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        edges.push_back({cost,{a,b}});
    }
    /* parent 초기화 */
    for(int i=1;i<=N;i++)
        parent[i] = i;

    /* edges 정렬 */
    sort(edges.begin(), edges.end());

    for(int i=0;i<edges.size();i++)
    {
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        int cost = edges[i].first;
        if(findParent(a) != findParent(b)){
            unionParent(a,b);
            ans+=cost;
        }
    }
    cout << ans;
    return 0;
}

• 핵심
  • MST(최소 신장 트리)를 찾는 문제니까 Kruskal, Prim을 사용