[BOJ알고리즘, C++]#1197_최소 스패닝 트리, MST, 크루스칼, 프림, 솔린

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 최소 신장 트리(Minimum Spanning Tree)

[자료구조]#6_그래프

 

Details

 

[정의] : 최소 신장 트리는 가중치 그래프 내 간선들이 갖는 가중치의 합이 최소가 되는 신장 트리.
[특징] : 최소 신장 트리 알고리즘으로 크루스칼, 프림, 그리고 솔린 알고리즘이 있습니다.

 

2. 크루스칼 활용 or 프림 활용 or 솔린 활용

 

[크루스칼 알고리즘] : 크루스칼 알고리즘은 간선 목록의 오름차순 정렬, 그리고 Union-Find만 기억하면 됩니다.
[프림 알고리즘] : 프림 알고리즘은 간선의 인접 정점을 탐색하며, 우선순위 큐를 활용합니다.
[솔린 알고리즘] : 솔린 알고리즘은 '집합' 중심 알고리즘으로, 최소 가중치 간선 목록과 Union-Find 연산

 

---

 

#3. 코드

 

1. 크루스칼

 

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

int V, E, answer;

// #1. 간선 구조체
struct Edge
{
	int from, weight, to;
	Edge(int from, int to, int weight)
	{
		this->from = from;
		this->to = to;
		this->weight = weight;
	}

	bool operator<(const Edge& RightEdge)
	{
		return weight < RightEdge.weight;
	}
};

// #2. Find 연산
int Find(int x, vector<int>& parent)
{
	if (parent[x] != x)
	{
		parent[x] = Find(parent[x], parent);
	}

	return parent[x];
}
// #3. Union 연산
void Union(int rootX, int rootY, vector<int>& parent, vector<int>& rank)
{

	if (rank[rootX] > rank[rootY])
	{
		parent[rootY] = rootX;
	}
	else if (rank[rootX] < rank[rootY])
	{
		parent[rootX] = rootY;
	}
	else
	{
		parent[rootX] = rootY;
		rank[rootY]++;
	}

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> V >> E;
    
    // #1. 간선 목록
    vector<Edge> edges;
    // #2. 부모 목록 : 부모를 자기 자신으로 초기화
    vector<int> parent(V+1);
    for(int i=1; i<=V; ++i)
        parent[i] = i;
    // #3. rank 목록 : 모두 0으로 초기화
    vector<int> rank(V+1, 0);
    
    // #4. 그래프 구성
    while(E--)
    {
        int from, to, weight;
        
        cin >> from >> to >> weight;
        edges.push_back(Edge(from, to, weight));
    }
    // #5. 간선을 weight 기준 오름차순 정렬
    sort(begin(edges), end(edges));
    
    // #6. MST 목록
    for(const auto& edge : edges)
    {
        // #6-1. from 정점과 to 정점의 루트 노드 찾기
        int rootX = Find(edge.from, parent);
        int rootY = Find(edge.to, parent);
        
        if(rootX != rootY)
        {
            answer += edge.weight;
            // #6-2. Union 연산
            Union(rootX, rootY, parent, rank);
        }
    }
    
    cout << answer;
    
    return 0;
}

 

2. 프림

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int V, E, answer;

// #1. Prim 알고리즘
void Prim(int start, vector<vector<pair<int,int>>>& graph)
{
    // #방문 여부
    vector<bool> visited(V+1, false);
    // 우선 순위 큐 : pair<int, int> 의 first 기준 최소힙
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    
    pq.push({0, start});
    // 우선순위 큐 순회
    while(!pq.empty())
    {
        int weight = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        if(!visited[cur])
        {
            visited[cur] = true;
            answer += weight;
            
            for(const auto& edge : graph[cur])
            {
                if(!visited[edge.second])
                {
                    pq.push(edge);
                }
            }
        }
    }
    
    cout << answer;
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> V >> E;
    
    // 2차원 vector 형식의 graph 선언
    vector<vector<pair<int,int>>> graph(V+1);
    // 그래프 구성
    for(int i=0; i<E; ++i)
    {
        int from, to, weight;
        
        cin >> from >> to >> weight;
        graph[from].push_back({weight, to});
        graph[to].push_back({weight, from});
    }
    // Prim 알고리즘 호출
    Prim(1, graph);
    
    return 0;
}

 

---