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

1197번 : 최소 스패닝 트리

---

문제 )

 

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

 

입력 :

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

 

 

 

출력 :

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

 

 

 

 

 

풀이)

MST를 이용하여 풀어주었다.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Edge라는 클래스를 만들어 간선을 관리
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;
    }
 
    // sort를 위한 연산자 오버로딩
    bool operator < (Edge& edge)
    {
        return this->distance < edge.distance;
    }
};
 
int par[10010];
vector<Edge> vec;
 
int find(int x)
{
    if (par[x] == x)
    {
        return x;
    }
    else
    {    // 경로 압축
        par[x] = find(par[x]);
        return par[x];
    }
}
 
void union_(int a, int b)
{
    a = find(a);
    b = find(b);
 
    par[a] = b;
}
 
 
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
 
    for (int i = 0; i < 10010; i++) par[i] = i;
 
    int v, e;
    cin >> v >> e;
 
    int a, b, c;
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b >> c;
        vec.push_back(Edge(a, b, c));
    }
 
    // 가중치가 작은 것부터 더해주기 위해
    sort(vec.begin(), vec.end());
 
    int count = 0;
    int rate = 0;
    for (int i = 0; i < e; i++)
    {
        a = vec[i].node[0];
        b = vec[i].node[1];
 
        // 부모가 같지 않다면
        if (find(a) != find(b))
        {
            union_(a, b);
            count++;
            rate += vec[i].distance;
        }
 
        // count가 v - 1개라면 모든 노드가 연결되었으므로
        if (count == v - 1)
        {
            cout << rate;
            return 0;
        }
    }
}
 

 

---

출처 : https://www.acmicpc.net/problem/1197 

1197번: 최소 스패닝 트리