1197-최소 스패닝 트리

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

자료구조 강의 시간에 얼핏 들었던 최소 스패닝 트리(MST, Minimum Spanning Tree)알고리즘을 공부할겸 해당 문제를 풀어보았습니다.

 

MST 알고리즘은 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 게시글과 [알고리즘] Kruskal 알고리즘 이란 게시글을 읽고 개념을 숙지하였습니다. 추가적으로 나동빈님의 강좌를 시청하였습니다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//1197: 최소 스패닝 트리
int V; //정점의 개수
int E; //간선의 개수

struct node
{
    int from;
    int to;
    int edge;
    node(int from, int to, int edge)
    {
        this->from = from;
        this->to = to;
        this->edge = edge;
    }

    bool operator <(node &node)
    {
        return this->edge < node.edge;
    }
};

vector<node> g;

int get_parent(vector<int>& parent, int i)
{
    if(parent[i] == i) return i;
    return parent[i] = get_parent(parent, parent[i]);
}

bool cycle_exist(vector<int>& parent, int a, int b)
{
    return get_parent(parent, a) == get_parent(parent, b);
}

//부모 노드를 병합
void union_parent(vector<int>& parent, int a, int b)
{
    a = parent[a];
    b = parent[b];
    
    if(parent[a] < parent[b]) parent[b] = a;
    else parent[a] = b;
    // if(parent[a] < parent[b])
    // {
    //     parent[b] = parent[a];
    // }
    // else
    // {
    //     parent[a] = parent[b];
    // }
}

int main()
{
    //freopen("1197.txt", "r", stdin);
    cin >> V >> E;

    for(int i = 0; i < E; i++)
    {
        int from;
        int to;
        int edge;

        cin >> from >> to >> edge;
        g.push_back(node(from, to, edge));
    }

    sort(g.begin(), g.end());

    //MST의 간선 개수는 노드 개수-1 과 항상 동일하다.
    //MST는 사이클이 형성될 수 없다.

    vector<int> parent(V + 1); // parent[i] : i번째 노드의 부모
    for(int i = 1; i < parent.size(); i++)
    {
        parent[i] = i;
    }

    int sum = 0;
    int num_edge = 0;
    for(node n:g)
    {
        if(cycle_exist(parent, n.from, n.to))
            continue;

        sum += n.edge;
        num_edge += 1;
        union_parent(parent, n.from, n.to);

        if(num_edge == V-1)
            break;
    }

    cout << sum;
    return 0;
}