[C++] 백준 1674 도시 분할 계획

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
 
int N = 0;
int M = 0;
int min = 100000001;
int parent[100001] = {};
std::vector<int> ansVec = {};
std::tuple<int, int, int> road[1000001] = {};
 
bool cmp(std::tuple<int, int, int> tuple1, std::tuple<int, int, int> tuple2)
{
    if (std::get<2>(tuple1) == std::get<2>(tuple2))
        return std::get<0>(tuple1) > std::get<0>(tuple2);
    else
        return std::get<2>(tuple1) < std::get<2>(tuple2);
}
 
int FindParent(int x)
{
    if (x == parent[x])
        return x;
 
    else 
        return parent[x] = FindParent(parent[x]);
}
 
void Union(int x, int y)
{
    x = FindParent(x);
    y = FindParent(y);
 
    if (x == y) 
        return;
 
    parent[y] = x;
}
 
bool SameParent(int x, int y)
{
    x = FindParent(x);
    y = FindParent(y);
 
    if (x == y) 
        return true;
 
    return false;
}
 
int main() 
{
    std::cin >> N >> M;
 
    for (int i = 0; i < M; ++i)
    {
        int start = 0;
        int end = 0;
        int cost = 0;
        std::cin >> start >> end >> cost;
 
        road[i] = {start, end, cost};
    }
 
    sort(road, road + M, cmp);
 
    for (int i = 1; i <= N; ++i)
    {
        parent[i] = i;
    }
 
    for (int i = 0; i < M; ++i)
    {
        if (!SameParent(std::get<0>(road[i]), std::get<1>(road[i])))
        {
            Union(std::get<0>(road[i]), std::get<1>(road[i]));
            ansVec.push_back(std::get<2>(road[i]));
        }
    }
 
    int ans = 0;
 
    for (int i = 0; i < ansVec.size() - 1; ++i)
    {
        ans += ansVec[i];
    }
 
    std::cout << ans;
 
    return 0;
}

 

크루스칼 알고리즘을 이용합니다. 두번째로 푸는 문제인데... 역시 감이 잘 안잡히네요...

제일 중요한 건 sort입니다. 짧은 순서대로 연결을 합니다.

연결이 되었을 경우 (부모가 있을 경우) 연결하지 않습니다.

연결이 되지 않을 경우 부모를 가장 처음 연결한 것으로 입력,

부모를 찾을 경우 가장 처음 연결한 부모로 연결할 수 있도록 만듭니다.

그리고 가장 마지막으로 긴 선만 제외한다면 마을을 두 개로 나눌 수 있습니다.