백준 16398 - 행성 연결, C++, 최소 스패닝 트리

16398번: 행성 연결

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

int n;
int parent[1001];
int cost[1001][1001];
vector<pair<int, pair<int, int>>> edge;

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

bool SameParent(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return true;
    return false;
}

void Merge(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;
    parent[x] = y;
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // input
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> cost[i][j];
        }
    }    
    
    // init
    for(int i = 1; i <= n; i++) 
        parent[i] = i;

    // edge
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            edge.push_back(make_pair(cost[i][j], make_pair(i, j)));
        }
    }

    // Make MST
    long long ans = 0;
    sort(edge.begin(), edge.end());

    for(int i = 0; i < edge.size(); i++){
        if(!SameParent(edge[i].second.first, edge[i].second.second)){
            ans += edge[i].first;
            Merge(edge[i].second.first, edge[i].second.second);
        }
    }

    cout << ans << '\n';
}

---

 평범함 MST 만드는 문제였다. 입력값이 많은 테케가 있는걸로 보이니 꼭 입출력 속도를 높여서 하도록 합시다.