[백준 1197번 / C++ / 크루스칼] 최소 스패닝 트리

"운영체제 CS 전공" 준비하시는 분께 도움을 드리고자 포스팅 하고 있습니다! 

관심 있으신 분들은 아래 링크 클릭!

 

'남이 읽는 CS/운영체제' 카테고리의 글 목록

---

최소 스패닝 트리(MST)는 최소한의 간선으로 모든 정점이 연결되어 있는 구조이다. 

 

MST 그래프를 구하기 위해서는 크루스칼과 프림 알고리즘이 존재하는데 

이번 문제에서는 크루스칼을 이용해서 구현하였다. 

 

먼저 모든 간선을 가중치 기준으로 오름차순으로 정렬한다

그리고 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하면 된다. 

단! 사이클이 형성 되지 않도록! 

 

Union-Find 알고리즘을 활용해보자. 처음 들어보신 분들도 분명히 계실거고 헷갈려 하시는 분들이 계실텐데 

어떻게 하는 것인지 간단하게 알아보고 자기것으로 만들어야한다. 

 

먼저, 방문해야할 노드가 5개가 있다고 가정하자. 

 

각 노드의 이름은 1,2,3,4,5번이다. 그리고 각 노드의 부모 노드는 현재 자기 자신의 번호로 초기화를 한다. 

이게 뭔말인지 아직 모를 수 있지만 일단 서로 연결되어 있지않다는 의미니까 계속 읽어보자! 

 

자! 아까 스패닝트리를 만드는 크루스칼 알고리즘은 모든 간선을 가중치 기준 오름차순이라고 했는데 이때 사이클이 형성 되지 않아야 한다고 언급했다. 그 말은 부모 노드가 달라야 한다는 뜻이다. 

 

쉽게 설명하자면,

 

만약, 1~5번 노드들의 가중치 정보들이 나와있는데 그 중에서 1번과 2번 노드를 연결하는 가중치가 제일 작다고 가정했을 때 1번과 2번을 바로 연결해야한다. 왜냐! 가중치가 제일 작은 정점들을 먼저 연결해야하니까! 

 

그래! 연결하면 끝인데 뭐 더해야해?? 의문을 가질 수 있는데 이때 사용하는 것이 Union-Find 알고리즘이다.

즉, 1번과 2번을 연결했을 때 어느 한쪽이 다른 노드의 번호를 저장해야한다는 뜻! 

 

예를들어, 1번 노드와 2번 노드를 합친다. 그러면 2번 노드에는 1번이라는 숫자를 저장한다. 

즉, 2번 자신은 1번 노드와 연결되어 있다는 뜻이다. 

 

이후 2번 노드와 3번 노드를 연결해야한다고 가정하자. 

이때 2번 노드는 현재 1번과 연결되어 있고 3번 노드는 아직 아무랑도 연결되어 있지 않다. 

 

그러면 3번과 2번 노드랑 연결을 하는데 여기서 2번 노드의 부모노드는 1번이라고 저장했지않는가 

그렇다면 3번노드 또한 자신의 부모 노드를 1번노드라고 적어 놓는 것이다. 

 

즉, 1번, 2번, 3번 노드는 서로 연결되어 있는데 부모노드는 셋다 1번으로 되어 있는 것이다. 

 

자 만약, 여기서 1번 노드와 3번 노드를 연결 정보가 주어져서 1번과 3번도 연결해야하는 상황이 발생할 수 있다

이때 1번 노드는 자기자신을 부모노드로 세팅해놨었고 3번 노드는 아까 2번 노드와 합칠 때 부모노드를 1번으로 세팅했었다. 

 

그러면 둘다 부모노드가 같네??? 

 

이 말은 두개의 노드와 연결된 최상단의 부모노드는 1번이라는 의미이며 또한 동일한 값이므로 같은 부모노드로부터 파생되었다는 의미다. 즉, 연결되어 있는 간선들을 타고타고 들어가다보면 만날 수 있다는 의미다.

 

그래서 1번노드와 3번 노드는 같은 부모 노드로부터 파생되었으니 연결되어있다는건데 1번과 3번을 또 연결해야 할까? 

아니! 연결하면 사이클이 생겨버리지. 

 

왜 싸이클이 생기는데?? 라고 물을 수 있는데 양쪽 검지손가락 손톱 끝으로 맞대고 ^ 이 모양 만들어본다. 

그리고 손톱 끝의 교차점이 부모노드이고 검지 손가락은 부모노드와 어떠한 정점으로 연결된 간선이다. 

그리고 엄지손가락 하나를 반대쪽 검지손가락 중간에 맞대본다. 

삼각형 생겨 안생겨!!?? 사이클이다

 

그러므로 같은 부모노드를 가진 노드 두개를 연결하면 안된다.   

 

---

 

코드와 개념이해가 잘 안되시는 분들은 아래 참조한 영상 링크를 통해서 먼저 학습을 하고 코드를 이해하길 추천합니다!

출처 : 동빈나 유튜브

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
int parent[10001];
int find(int x) {
	if (parent[x] == x)return x;
	else return parent[x] = find(parent[x]); 
}
void uni(int x, int y) {
	x = find(x); 
	y = find(y); 
	parent[y] = x; 
}
bool sameparent(int x, int y) {
	x = find(x); 
	y = find(y); 
	if (x == y)return true;
	else return false; 
}
int main() {
	int vertex, e; 
	cin >> vertex >> e;
	int result = 0; 
	vector<pair<int, pair<int, int>>>v; 
	for (int i = 0; i < e; i++) {
		int from, to, cost; 
		cin >> from >> to >> cost; 
		v.push_back({ cost,{from,to} }); 
	}
	sort(v.begin(), v.end()); 
	for (int i = 1; i <= vertex; i++)parent[i] = i; 
	for (int i = 0; i < v.size(); i++) {
		if (!sameparent(v[i].second.first, v[i].second.second)) {
			uni(v[i].second.first, v[i].second.second); 
			result += v[i].first; 
		}
	}
	cout << result; 
}

1197번: 최소 스패닝 트리