백준 1197 - 최소 스패닝 트리

문제

 

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

1197번: 최소 스패닝 트리

 

 

풀이

 

최소 스패닝 트리를 구하는 알고리즘은 크루스칼과 프림 알고리즘이 있다. 

 

1. 프림 알고리즘은 정점 집합을 기준으로 트리를 확장을 한다. 현재 정점을 기준으로 연결된 정점 중에서 가중치가 제일 작은 간선으로 연결된 정점을 추가해야 되는데, 이 때 우선순위 큐를 이용해서 정점을 추가한다. 우선순위 큐에 가중치를 기준으로 정점들을 저장하면 가중치가 제일 작은 다음 정점을 쉽게 알아낼 수 있다. 이 과정을 모든 정점을 방문할 때까지 반복하면 된다. 모든 정점을 방문하면 최소 스패닝 트리가 만들어지게 된다. 

 

2. 크루스칼 알고리즘은 간선의 가중치를 기준으로 오름차순으로 정렬한 후 사이클을 생성하지 않는 간선들을 선택함으로써 최소 스패닝 트리를 생성한다. 사이클 여부를 검사하기 위해서 유니온-파인드를 사용한다. 모든 간선에 대해서 유니온-파인드 과정을 진행해주면 최소 스패닝 트리에 대한 정보를 얻을 수 있다.

 

 

코드

 

프림 알고리즘

 

 

크루스칼 알고리즘

 

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
struct Edge
{
    int u, v, w;
 
    bool operator<(struct Edge & cmp)
    {
        return w < cmp.w;
    }
};
 
int V, E;
vector<Edge> graph;
int result;
int parent[10001], size[10001];
 
int findParent(int v)
{
    if (v == parent[v]) return v;
    return parent[v] = findParent(parent[v]);
}
 
void unionVertex(int u, int v)
{
    int p1 = findParent(u);
    int p2 = findParent(v);
 
    if (p1 != p2)
    {
        if (size[p1] < size[p2]) swap(p1, p2);
 
        parent[p2] = p1;
        size[p1] += size[p2];
        size[p2] = 0;
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> V >> E;
 
    Edge e;
    for (int i=0; i<E; i++)
    {
        cin >> e.u >> e.v >> e.w;
        graph.push_back(e); 
    }
 
    sort(graph.begin(), graph.end());
 
    for (int i=1; i<=V; i++) parent[i] = i;
    
    for (int i=0; i<E; i++)
    {
        e = graph[i];
 
        if (findParent(e.u) != findParent(e.v))
        {
            unionVertex(e.u, e.v);
            result += e.w;
        }
    }
 
    cout << result;
 
    return 0;
}