네트워크 연결 - 1922번 백준

문제

문제 난이도: 골드 4

문제 분류: 최소 스패닝 트리

 

문제 리뷰

최소 스패닝 트리!!! 그리디를 이용한다.

그리디를 이용하기 위해서 유니온 파인드 알고리즘(경로 압축, 랭크 압축을 필요시 추가 구현해야한다. 난 여기서 경로 압축만 쉬워서.. 구현했다)을 사용(트리로 구현, 배열로 구현하는 방법도 있음.)한다.

내일은 프림 알고리즘을 배워보자꾸나

 

문제 난이도

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <deque>
#include <queue>
#include <unordered_map>

using namespace std;

//Global Variable
vector<vector<int>> Edges;
int RootNode[1001];
int NodeNum, EdgeNum;
//Initializing for Optimization
void Init() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int Find(int x) {
    if (RootNode[x] == x)
    {
        return x;
    }
    else {
        return RootNode[x] = Find(RootNode[x]);
    }
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y)
    {
        RootNode[y] = x;
    }
}

vector<vector<int>> Kruskal() {
    vector<vector<int>> MSTEdges;
    for (int i = 0; i < Edges.size(); ++i) {
        vector<int> tmpv = Edges[i];
        if (Find(tmpv[1]) == Find(tmpv[2])) continue;
        MSTEdges.push_back(tmpv);
        if (MSTEdges.size() == NodeNum - 1) return MSTEdges;
        Union(tmpv[1], tmpv[2]);
    }

}

int main()
{
    //Initialize for fast io
    Init();
    //Init root node itself.
    for (int i = 0; i < 1001; i++)
    {
        RootNode[i] = i;
    }
    //Num Input
    
    cin >> NodeNum >> EdgeNum;
    //Edge Input
    for (int i = 0; i < EdgeNum; ++i) {
        int s, e, w;
        cin >> s >> e >> w;
        s--; e--;
        // 가중치 - 시작점 - 끝점
        Edges.push_back({ w, s ,e });
        //Union(e , s);
    }
    //Sort
    sort(Edges.begin(), Edges.end(), less<vector<int>>());
    long long int MinimumLength = 0;
    //Kruskal
    vector<vector<int>> KruskalMSTVec = Kruskal();
    //Sum Minimum Distance
    for (vector<int> v : KruskalMSTVec) {
        MinimumLength += v[0];
    }
    cout << MinimumLength;

}