이번에는 MST를 풀어보자. MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다.
이번 문제를 풀기 위해서는 MST를 알기 이전에 Spanning Tree에 대해서 이해해야한다.
Spanning Tree
- 간선 수가 가장 작게 연결된다. 만약 정점이 V개라면 V-1개로 연결된 트리
- 사이클이 존재하지 않는다.(트리의 형태)
Minimum Spanning Tree
- 값이 가장 작은 간선을 이용하여 만든 Spanning Tree
- 간선 가중치 합이 최소여야 한다.
- 사이클이 존재하지 않는다.
- 크루스칼 알고리즘과 프림알고리즘이 존재한다.
개인적으로 크루스칼(탐욕적 방법) 알고리즘이 쉽고 편하다고 느꼈기 때문에 크루스칼 알고리즘만 공부하기로 했다.
크루스칼 알고리즘은 아래와 같은 단계로 진행한다.
- 코스트(간선의 가중치 혹은 거리)별로 정렬한다.(오름차순)
- 하나씩 꺼내서 각 정점이 서로 같은 그룹에 속하는지 판별한다. (파인드 함수 사용)
2-1. 다른 정점에 속하는 경우 같은 그룹으로 묶어준다. (유니온 함수 사용)
2-2. 같은 정점에 속하는 경우 연산을 진행하지 않는다. - 2단계를 반복하며 모든 간선을 체크한다.
여기서 중요한것은 같은 그룹인지 어떻게 판단할 건지, 같은 그룹으로 어떻게 묶을 건지이다. 해당 내용은 이전에 유니온 파인드 글로 설명을 해 놓았다.
https://guccin.tistory.com/110
그럼 이제 끝이다. 그냥 코드를 작성해 주면된다.
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int V, E;
vector<pair<int, pair<int, int>>> Edge;
int parent[10001];
int find_function(int node) {// 해당 값이 어떤 루트 노드에 속하는지 알아낸다.
if (node == parent[node])//자신의 노드가 부모라면 루트 노드라는 뜻
return node;
return parent[node] = find_function(parent[node]);// 부모 노드를 타고 올라가면서 루트 노드 갱신
}
void union_function(int node1, int node2) {// 한 노드의 부모 노드에 편입시킨다.
int root1 = find_function(node1);
int root2 = find_function(node2);
parent[root2] = root1;
}
int main() {
cin >> V >> E;
int a, b, c;
for (int i = 0; i < E; i++)
{
cin >> a >> b >> c;
Edge.push_back({ c, { a,b } });
}
// 크루스칼을 사용하기 위해 가중치별 정렬
sort(Edge.begin(), Edge.end());//오름차순 정렬
for (int i = 1; i <= V; i++)
{
parent[i] = i; // 모든 노드를 자신이 루트가 되도록 만든다.
}
// 크루스칼의 유니온파인드 진행
int sum = 0;
for (int i = 0; i < E; i++)
{
pair<int, pair<int, int>> tEdge = Edge[i];
if (find_function(tEdge.second.first) == find_function(tEdge.second.second)) {// 노드가 서로 같은 그룹인경우 버린다.
}
else {//노드가 서로 다른 그룹이면 합친다.
union_function(tEdge.second.first, tEdge.second.second);
sum += tEdge.first;
}
}
cout << sum;
}
find함수와 union함수는 간단하기 때문에 외우면 될 것 같고, 살짝 어려운 점은 find함수에서 "return parent[node] = find_function(parent[node]);" 인데 이 부분은 실제 손 디버깅을 해보면 같은 그룹에서의 각 노드의 부모를 루트로 변경시켜주는 작업이라고 이해하면 될 듯 하다.
결론 : MST는 그다지 어렵지 않으나 응용하는 경우 굉장히 어려울 것 같다. 그러니 유니온 파인드나 부수적인 단계라도 잘 숙지해 놓자.
'알고리즘' 카테고리의 다른 글
[python3] 백준 10844 풀이 ( 쉬운 계단 수, 다이나믹 프로그래밍, 이차 배열) (0) | 2021.08.05 |
---|---|
[c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 ) (0) | 2021.08.04 |
[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드) (0) | 2021.07.26 |
[python3] 백준 1967 풀이 (트리의 지름, DFS) (0) | 2021.07.26 |
[python3] 백준 1937 풀이 (욕심쟁이 판다, DFS, DP) (0) | 2021.07.26 |