[BOJ알고리즘, C++]#1922_네트워크 연결, MST, 최소 신장 트리, 크루스칼, 프림, 솔린

 

#1. 문제

 

 

---

 

#2. 풀이

 

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

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

 

최소 신장 트리는 가중치 그래프 내 간선 목록의 가중치 합이 최소가 되는 신장 트리를 의미합니다. 따라서, 최소 신장 트리는 최소한의 간선을 이용해 부분 그래프(트리)를 형성하는 동시에 가중치의 합이 최소가 되는 신장 트리입니다. 대표적인 MST 알고리즘은 세 가지입니다. - 크루스칼, 프림, 솔린

 

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

 

1. 크루스칼 : 크루스칼은 간선 목록의 오름차순 정렬, 그리고 Union-Find 연산을 활용합니다.
2. 프림 : 프림은 인접 정점들 중 최소 가중치 간선을 찾고, 우선순위 큐를 활용해 탐색 순서를 결정합니다.
3. 솔린 : 솔린은 최소 가중치 간선 목록을 작성하고, Union-Find 연산을 반복합니다.

 

---

 

#3. 코드

 

1. 크루스칼

 

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

int N, M;

// 간선 구조체
struct Edge
{
    int from, to, weight;
    
    bool operator< (const Edge& other)
    {
        return weight < other.weight;
    }
};

// Union-Find
int Find(int x, vector<int>& parent)
{
	if (parent[x] != x)
	{
		parent[x] = Find(parent[x], parent);
	}

	return parent[x];
}
// Union-Find
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]++;
	}

}

void Kruskal(vector<Edge>& edges)
{
    // parent, rank -> Union-Find 연산
    vector<int> parent(N+1);
    vector<int> rank(N+1, 0);
    int MSTWeight = 0;
    // parent 초기화
    for(int i=1; i<=N; ++i)
        parent[i] = i;
    
    // 가중치 기준 오름차순 정렬
    sort(begin(edges), end(edges));
    
    // 간선 목록 순회
    for(const auto& edge : edges)
    {
        int rootX = Find(edge.from, parent);
        int rootY = Find(edge.to, parent);
        
        if(rootX != rootY)
        {
            MSTWeight += edge.weight;
            Union(rootX, rootY, parent, rank);
        }
    }
    
    cout << MSTWeight;
    
}

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

    cin >> N >> M;
    
    // vector 형식의 간선 목록
    vector<Edge> edges(M);
    // 간선 목록 초기화
    for(int i=0; i<M; ++i)
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    
    Kruskal(edges);
    
    return 0;
}

 

2. 프림

 

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

int N, M;

void Prim(unordered_map<int, vector<pair<int,int>>>& graph)
{
    // 방문 여부
    vector<bool> visited(N+1, false);
    // 우선 순위 큐, 가중치 기준 최소 힙
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    int MSTWeight = 0;
    
    // 1을 시작 노드로, 우선순위 큐에 삽입
    pq.push({0, 1});
    
    while(!pq.empty())
    {
        int weight = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
     
        if(visited[cur])
            continue;
        
        visited[cur] = true;
        MSTWeight += weight;
        
        // pair<int, int> : 가중치 + 인접 정점
        for(const auto& pair : graph[cur])
        {
            pq.push(pair);
        }
    }
    
    cout << MSTWeight;
    
}

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

    cin >> N >> M;
    
    // a 정점에 대해서 pair.first = 인접 정점, pair.second = 가중치
    unordered_map<int, vector<pair<int,int>>> graph;
    
    while(M--)
    {
        int a, b, c;
        
        cin >> a >> b >> c;
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
    }
    
    Prim(graph); 
    
    return 0;
}

 

3. 솔린

 

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

// #1. 간선 구조체
struct Edge {
	int src, dest, weight;
};

// #2. Find 연산
int find(vector<int>& parent, int i) {
	if (parent[i] == i)
		return i;
	return parent[i] = find(parent, parent[i]);
}
// #3. Union 연산 
void Union(vector<int>& parent, vector<int>& rank, int x, int y) {
	int rootX = find(parent, x);
	int rootY = find(parent, y);

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

void sollin(vector<Edge>& edges, int N, int M) {
	// #1.parent 목록, rank 목록 : Union-Find의 최적화,
	vector<int> parent(N + 1), cheapest(N + 1), rank(N + 1, 0);

	// #2. 총 컴포넌트 수, MST의 가중치 합
	int numComponents = N, MSTweight = 0;

	// #3. 부모 목록 초기화
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	// #4. 총 컴포넌트가 1개가 될 때까지 진행되는 솔린 알고리즘
	while (numComponents > 1) {
		fill(cheapest.begin(), cheapest.end(), -1);

		// 1.	간선 목록 순회하며, 각 간선의 시작 노드와 도착 노드가 속해 있는 트리/집합의 루트/대표 노드
		//		를 인덱스로, 해당 트리/집합의 간선들 중 최소 가중치를 갖는 간선을 찾는다.
		for (int i = 0; i < M; i++) {
			int set1 = find(parent, edges[i].src);
			int set2 = find(parent, edges[i].dest);

			if (set1 == set2)
				continue;
			else {
				if (cheapest[set1] == -1 || edges[cheapest[set1]].weight > edges[i].weight)
					cheapest[set1] = i;
				if (cheapest[set2] == -1 || edges[cheapest[set2]].weight > edges[i].weight)
					cheapest[set2] = i;
			}
		}

		// 2.	각 집합의 최소 가중치 목록을 순회하며, 각 최소 가중치 간선의 시작 노드와 도착노드가
		//		속한 트리/집합의 루트/대표 노드들을 구해 Union 연산하여, 두 집합을 합친다.
		for (int i = 1; i <= N; i++) {
			if (cheapest[i] != -1) {
				int set1 = find(parent, edges[cheapest[i]].src);
				int set2 = find(parent, edges[cheapest[i]].dest);

				if (set1 == set2)
					continue;
				MSTweight += edges[cheapest[i]].weight;
				Union(parent, rank, set1, set2);
				numComponents--;
			}
		}
	}

	cout << MSTweight;
}

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

	int N, M;
	cin >> N >> M;

	vector<Edge> edges(M);

	for (int i = 0; i < M; i++)
		cin >> edges[i].src >> edges[i].dest >> edges[i].weight;

	sollin(edges, N, M);

	return 0;
}

 

---