[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드)

이번에는 MST를 풀어보자. MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다.

이번 문제를 풀기 위해서는 MST를 알기 이전에 Spanning Tree에 대해서 이해해야한다.

Spanning Tree

1. 간선 수가 가장 작게 연결된다. 만약 정점이 V개라면 V-1개로 연결된 트리
2. 사이클이 존재하지 않는다.(트리의 형태)

Minimum Spanning Tree

1. 값이 가장 작은 간선을 이용하여 만든 Spanning Tree
2. 간선 가중치 합이 최소여야 한다.
3. 사이클이 존재하지 않는다.
4. 크루스칼 알고리즘과 프림알고리즘이 존재한다.

개인적으로 크루스칼(탐욕적 방법) 알고리즘이 쉽고 편하다고 느꼈기 때문에 크루스칼 알고리즘만 공부하기로 했다.
크루스칼 알고리즘은 아래와 같은 단계로 진행한다.

1. 코스트(간선의 가중치 혹은 거리)별로 정렬한다.(오름차순)
2. 하나씩 꺼내서 각 정점이 서로 같은 그룹에 속하는지 판별한다. (파인드 함수 사용)
   2-1. 다른 정점에 속하는 경우 같은 그룹으로 묶어준다. (유니온 함수 사용)
   2-2. 같은 정점에 속하는 경우 연산을 진행하지 않는다.
3. 2단계를 반복하며 모든 간선을 체크한다.

여기서 중요한것은 같은 그룹인지 어떻게 판단할 건지, 같은 그룹으로 어떻게 묶을 건지이다. 해당 내용은 이전에 유니온 파인드 글로 설명을 해 놓았다.
https://guccin.tistory.com/110

[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드)

 

 

그럼 이제 끝이다. 그냥 코드를 작성해 주면된다.

#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는 그다지 어렵지 않으나 응용하는 경우 굉장히 어려울 것 같다. 그러니 유니온 파인드나 부수적인 단계라도 잘 숙지해 놓자.