[C++] 백준 1197 최소 스패닝 트리

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
 
int V = 0;
int E = 0;
 
int answer = 0;
int parent[10001] = {};
std::vector<std::tuple<int, int,int>> graph = {};
 
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<1>(tuple2);
 
    else
        return std::get<2>(tuple1) < std::get<2>(tuple2);
}
 
int FindParent(int x)
{
    if (parent[x] == x)
        return x;
 
    else 
        return parent[x] = FindParent(parent[x]);
}
 
bool ParentCheck(int x, int y)
{
    x = FindParent(x);
    y = FindParent(y);
 
    if (x == y) 
        return true;
 
    else
    {
        parent[y] = x;
 
        return false;
    }
}
 
int main(void)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cin >> V >> E;
 
    graph.resize(E);
 
    for (int i = 0; i < E; ++i)
    {
        int start = 0;
        int end = 0;
        int cost = 0;
        std::cin >> start >> end >> cost;
 
        graph[i] = { start, end, cost };
    }
 
    sort(graph.begin(), graph.end(), cmp);
 
    for (int i = 1; i <= V; ++i)
    {
        parent[i] = i;
    }
 
    for (int i = 0; i < E; ++i)
    {
        if (!ParentCheck(std::get<0>(graph[i]), std::get<1>(graph[i])))
        {
            answer = answer + std::get<2>(graph[i]);
        }
    }
 
    std::cout << answer;
 
    return 0;
}
 

 

문제 자체를 이해하기 어려웠습니다.

트리에 내부 순환하는 모든 간선들을 제거하고 가장 짧은 것들만 남기는 게 목적입니다.

그렇기 때문에 간선들의 비용을 가장 짧은 순서로 정렬해놓고 작은 순서대로 간선들을 설정해놓습니다.

그렇게 만들면 연결된 간선 중에 긴 간선들은 제거되면서 가장 짧은 간선들만 남습니다.