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

문제

풀이

• 크루스칼 알고리즘을 이용하였다. 
  • 가중치가 작은 순서대로 검사할 수 있도록 간선을 가중치의 오름차순으로 정렬한다.
  • 검사하는 간선이 사이클을 만들지 않다면 간선을 선택한다. 
  • 간선이 선택되면 선택된 간선의 노드를 같은 부모로 설정한다.
  • 모든 간선을 검사하거나, 간선이 (총 노드의 수 - 1)만큼 선택되었다면 종료된다. 

코드

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

using namespace std;

typedef struct
{
    int v1;
    int v2;
    int dist;
}edge;

int parent[10001];

bool compare(const edge edge1, const edge edge2)
{
    return edge1.dist < edge2.dist;
}

// v의 최상위 부모 노드를 반환
int getParent(int v)
{
    if (parent[v] == v)
    {
        return v;
    }

    return getParent(parent[v]);
}

// 현재 사이클이 생기는지(부모 노드가 같은지) 확인
bool Cycle(int v1, int v2)
{
    v1 = getParent(v1);
    v2 = getParent(v2);
    return v1 == v2;
}

// v1과 v2의 부모 노드를 같게 설정
void Union(int v1, int v2)
{
    int p1 = getParent(v1);
    int p2 = getParent(v2);

    if (p1 < p2)
    {
        parent[p2] = p1;
    }
    else
    {
        parent[p1] = p2;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int V, E;
    vector<edge> edges;
    long long answer = 0;

    cin >> V >> E;

    for (int i = 0; i < E; ++i)
    {
        int A, B, C;
        cin >> A >> B >> C;

        edges.push_back({ A, B, C });
    }

    // 가중치가 작은 순으로 정렬
    sort(edges.begin(), edges.end(), compare);
    // 초기 부모는 자신으로 설정
    for (int i = 1; i <= V; ++i)
    {
        parent[i] = i;
    }

    for (edge e : edges)
    {
        // 사이클이 생기지 않는다면 간선을 선택하고 Union
        if (!Cycle(e.v1, e.v2))
        {
            answer += e.dist;
            Union(e.v1, e.v2);
        }
    }

    cout << answer;

    return 0;
}