[알고리즘 문제] 백준1197 - 최소 스패닝 트리

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

최소 스패닝이란 모든 노드가 연결되면서 그 간선들의 합이 최소가 되는 트리입니다. 각 간선의 정보를 가중치가 작은순으로 정렬하고 사이클이 형성되지 않도록 간선을 하나씩 추가해주면 됩니다. 여기서 사이클의 형성여부는 각 노드의 부모값이 같은지를 확인하면 되며 코드상에서는 이를 parent[]로 표현하였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int parent[10001];

class Edge
{
public:
    int node[2];
    int distance;
    Edge(int a, int b, int distance)
    {
        this->node[0] = a;
        this->node[1] = b;
        this->distance = distance;
    }
    bool operator<(Edge &edge)
    {
        return this->distance < edge.distance;
    }
};

int getParent(int n) // n노드의 부모 노드를 확인
{
    if (n == parent[n])
    {
        return n;
    }
    return parent[n] = getParent(parent[n]);
}
int main()
{
    int V, E;
    cin >> V >> E;

    int ans = 0;
    vector<Edge> vec;

    for (int i = 0; i < E; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        vec.push_back(Edge(a, b, c));
    }

    for (int i = 1; i <= V; i++) // 각 노드의 부모노드를 초기화, 처음에는 자신이 자신의 부모노드
    {
        parent[i] = i;
    }

    sort(vec.begin(), vec.end()); // 가중치가 작은 순으로 정렬

    for (int i = 0; i < vec.size(); i++)
    {
        int a = getParent(vec[i].node[0]);
        int b = getParent(vec[i].node[1]);

        if (a == b) // 부모가 같으면 사이클이 형성되므로 pass
        {
            continue;
        }
        if (a > b) // 부모노드 중 더 작은 값을 기준으로 잡음
        {
            parent[a] = b;
        }
        else
        {
            parent[b] = a;
        }
        ans += vec[i].distance;
    }

    cout << ans << endl;
    return 0;
}