๐ ์ต์์ ์ฅํธ๋ฆฌ (Minimum Spanning Tree)
- ์ ์ฅํธ๋ฆฌ : ๊ทธ๋ํ G์ ๋ ธ๋ V๋ฅผ ๋ชจ๋ ํฌํจํ๋ E์ ์ํ๋ ์์ง๋ฅผ ์ฌ์ฉํด ๋ง๋ ํธ๋ฆฌ
- ์ต์์ ์ฅํธ๋ฆฌ : ๊ฐ์ค๊ทธ๋ํ G์ ์ ์ฅํธ๋ฆฌ ์ค์์ ํธ๋ฆฌ์ ์ํ ๊ฐ์ค์น์ ํฉ์ ์ต์๋ก ํ๋ ์ ์ฅ ํธ๋ฆฌ
- ์ต์์ ์ฅํธ๋ฆฌ๋ฅผ ๋ง๋๋ 2๊ฐ์ง ๋ฐฉ๋ฒ : Prim's Algorithm, Kruskal's Algorithm
์ต์์ ์ฅํธ๋ฆฌ์ ๊ฐ์ ๊ฐ์๋ (์ ์ ์ ์ - 1) ์ด๋ค. (N-1๊ฐ์ ๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด ํ์ฐ์ ์ผ๋ก ๋ชจ๋ ๋ ธ๋๊ฐ ์ฐ๊ฒฐ๋๋ค)
๊ฐ์ ๋ค์ ๊ฐ์ค์น ํฉ์ด ์ต์์ธ ๊ฒฝ์ฐ ์๋ก ๋ค๋ฅธ ์ต์์ ์ฅํธ๋ฆฌ๊ฐ ํ๋ ์ด์ ์์ ์ ์๋ค.
๐ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ (Kruskal's Algorithm)
๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์์ ๊ฐ์ ๋ถํฐ ์ฐจ๋ก๋๋ก ๊ฐ์ ์ ์ ํํด ๋๊ฐ๋ ๋ฐฉ๋ฒ์ผ๋ก, ํ์์ (greedy) ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๋ค.
๋งค ๋จ๊ณ ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์์ ๊ฐ์ ์ ์ฐ๊ฒฐํ๋ฉฐ, ์ด์ ๋จ๊ณ์์ ๋ง๋ค์ด์ง ์ ์ฅํธ๋ฆฌ์๋ ์๊ด์์ด ์ต์ ๊ฐ์ ์ ์ ํํ๋ค.
ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ํต์ฌ์ ์์ง๋ฅผ ์ ๋ ฌํ๋ ๊ฒ์ ์๋ค. ์์ง๋ฅผ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํด์ ๊ฐ์ค์น๊ฐ ๊ฐ์ฅ ์์ ์์ง ์์๋๋ก ๋ ธ๋๋ฅผ ์ด์ด๋๊ฐ๋ค. ์์ง ์ ๋ ฌ์ O(ElogE)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
์ด๋ ์ฌ์ดํด์ ํ์ฑํ์ง ์๋ ์์ง๋ฅผ ์ ํํด์ผ ํ๋ค. ์ฌ์ดํด์ ํ์ฑํ๊ฒ ๋๋ฉด N-1๊ฐ์ ๊ฐ์ ์ผ๋ก N๊ฐ์ ์ ์ ์ ์ด์ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค. ์ฌ์ดํด์ ํ์ฑ ์ฌ๋ถ๋ Union-Find ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ธํ๋ค.
Union-Find ์๊ณ ๋ฆฌ์ฆ์ ๋ ์ ์ ์ ๋ถ๋ชจ๊ฐ ๊ฐ๋ค๋ฉด ์ฌ์ดํด์ด ํ์ฑ๋๋ ๊ฒ์ด๊ณ , ๋ ์ ์ ์ ๋ถ๋ชจ๊ฐ ๋ค๋ฅด๋ค๋ฉด ์ฌ์ดํด์ด ํ์ฑ๋์ง ์๋ ๊ฒ์ ์ด์ฉํ๋ค. ํฌ๊ฒ Union(x, y)์ Find(x), Find(y)๋ก ๋๋ ๋ณผ ์ ์๋ค. Find(x)๋ฅผ ํตํด x์ ๋ถ๋ชจ๋ ธ๋(root๋ ธ๋)๋ฅผ ํ์ธํ๊ณ , x์ y์ ๋ถ๋ชจ๋ ธ๋๋ฅผ ๋น๊ตํด Unionํ๋ ๋ฐฉ์์ด๋ค. Union(x, y) ์์๋ ๋ ๋ ธ๋์ root๋ ธ๋๊ฐ ๊ฐ๋ค๋ฉด ์ด๋ฏธ ๊ฐ์ ํธ๋ฆฌ์ด๋ฏ๋ก ๋ค๋ฅธ ๊ฑธ ํด์ค ํ์๊ฐ ์๊ณ , root๋ ธ๋๊ฐ ๋ค๋ฅด๋ค๋ฉด x์ root๋ ธ๋๊ฐ y๊ฐ ๋๋๋ก ์ค์ ํด์ค๋ค.
+ union-find๋ ๊ตฌ๊ธ๋งํด์ ์ฐพ์๋ณธ๊ฑฐ๋ผ ์๋ฒฝํ๊ฒ ์ดํดํ์ง ์์ ๊ฑฐ ๊ฐ๋ค. ๋์ค์ ๋ค์ ๋ด์ผ์ง
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 10000;
int v, e;
int parent[MAX + 1];
pair<int, pair<int, int>> edge[100000];
// n๊ฐ์ ์์๊ฐ ๊ฐ๊ฐ์ ์งํฉ์ ํฌํจ๋์ด ์๋๋ก ์ด๊ธฐํ
void Set() {
for(int i = 1; i <= MAX; i++) {
parent[i] = i;
}
}
int Find(int x) {
// root์ธ ๊ฒฝ์ฐ x๋ฅผ ๋ฐํ
if(parent[x] == x) return x;
// ์๋๋ฉด root๋ฅผ ์ฐพ์๊ฐ
return parent[x] = Find(parent[x]);
}
// ๋ ์์ x, y๊ฐ ์ฃผ์ด์ง ๋ ์ด๋ค์ด ์ํ ๋ ์งํฉ์ ํ๋๋ก ํฉ์นจ
// x์ y์ ์์๊ฐ ๋ค์ด์ค๋ฉด ๊ฐ๊ฐ์ root ๋
ธ๋๋ฅผ ์ฐพ์์ฃผ๊ณ
// ๋ root ๋
ธ๋๊ฐ ๊ฐ์ง ์๋ค๋ฉด x์ root ๋
ธ๋๋ฅผ y๋ก ์ค์ ํด์ค๋ค
void Union(int x, int y) {
int xParent = Find(x);
int yParent = Find(y);
if(xParent == yParent) return; // root๊ฐ ๊ฐ๋ค๋ฉด ์ด๋ฏธ ๊ฐ์ ํธ๋ฆฌ
parent[xParent] = yParent; // u์ root๊ฐ v๊ฐ ๋๋๋ก
}
int main()
{
cin >> v >> e;
Set();
for(int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
edge[i].first = c;
edge[i].second.first = a;
edge[i].second.second = b;
}
sort(edge, edge + e);
int weight = 0;
int count = 0;
for(int i = 0; i < e; i++) {
if(Find(edge[i].second.first) != Find(edge[i].second.second)) {
weight += edge[i].first;
Union(edge[i].second.first, edge[i].second.second);
count++;
}
if(count == v - 1) break;
}
cout << weight;
return 0;
}
๐ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ (Prim's Algorithm)
ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ ํ๋๋ฅผ ์์์ ์ผ๋ก ๋๊ณ , ์ด์ ๋จ๊ณ์์ ์์ฑ๋ ์ ์ฅํธ๋ฆฌ์ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ค ๊ฐ์ค์น๊ฐ ์ต์์ธ ๊ฐ์ ์ ์ ํํ๋ ๋ฐฉ๋ฒ์ด๋ค. ํด๋น ๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์ ์ ์ด ํ์ฌ์ ์ ์ฅํธ๋ฆฌ์ ์ํด์์ง ์๋ค๋ฉด ์ ํํ๋ค. ์ด๋ ์ง๊ธ๊น์ง์ ์ ์ฅํธ๋ฆฌ์ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ค์ ์ต์์ธ ๊ฒ์ ์ฐพ์ผ๋ ค๋ฉด ์ต์ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ฉด ๋น ๋ฅด๊ฒ ์ฒ๋ฆฌํ ์ ์๋ค.
๋ํ ์์ง = ๋ ธ๋์ ์ - 1 ์ด ๋ ๋๊น์ง ๋ฐ๋ณตํด ์์ง๋ฅผ ํ์ํด ๋๊ฐ๋ค. ์ต์๊ฐ์ ์ฐพ์ ๋ ์ต์ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๋ค๋ฉด O(nlogn)์ ์๊ฐ๋ณต์ก๋๊ฐ ๋ฐ์ํ๋ค. ์ด์ ๋จ๊ณ์์ ๋ง๋ ์ ์ฅํธ๋ฆฌ์ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ ๋ชจ๋ ์ต์์ฐ์ ์์ ํ์ ์ฝ์ ํด ๊ทธ ์ค ์ต์๊ฐ์ ์ฐพ์์ผ ํ๋ฏ๋ก ์ฌ๊ท์ ์ผ๋ก ๊ตฌํํด๋ณผ ์ ์๋ค. ์ฐพ์ ์ต์๊ฐ์ผ๋ก ๋ ธ๋์ ์ ์ฅํธ๋ฆฌ๋ฅผ ์ฐ๊ฒฐํ๊ณ , ๊ทธ ๋ ธ๋๋ฅผ ๊ธฐ์ค์ผ๋ก Prim() ํจ์๋ฅผ ์ฌ๊ท์ ์ผ๋ก ํธ์ถํ๋ค.
๊ฐ์ธ์ ์ผ๋ก ํฌ๋ฃจ์ค์นผ๋ณด๋ค ํ๋ฆผ์๊ณ ๋ฆฌ์ฆ์ด ์ข ๋ ์ดํดํ๊ธฐ๋ ์ฌ์ด ๋ฏํ๋ค. ์ต์ ์ฐ์ ์์ ํ๋ ํธ๋ฆฌ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง๋ ์ต์ํ์ด๋ผ๊ณ ๋ด๋ ๋๋๋ฐ, ์๊ฐ๋ณต์ก๋ O(nlogn)์ ๊ฐ์ง๋ ์ต์๊ฐ์ฐพ๋ ๋ฐฉ๋ฒ์ด๋ผ๊ณ ์๊ฐํ๊ณ ๋๊ธฐ๋ฉด ๋ ๊ฑฐ ๊ฐ๋ค. "์ต์" ์ฐ์ ์์ ํ๋ฅผ ๊ตฌํํ๋ ค๋ฉด ๋น๊ตํจ์๋ก greater<type>์ ์ถ๊ฐํด์ฃผ๊ธฐ!
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int v, e, sum;
vector<vector<pair<int, int>>> edge(10001);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqueue;
bool visited[10001];
void Prim(int v) {
visited[v] = true;
// ์ ์ v์ ์ฐ๊ฒฐ๋ ๊ฐ์ ์ ํ์ ๋ด๋๋ค
for(auto a: edge[v]) {
if(!visited[a.second]) {
pqueue.push({a.first, a.second});
}
}
while(!pqueue.empty()) {
pair<int, int> w = pqueue.top();
pqueue.pop();
if(!visited[w.second]) {
sum += w.first;
Prim(w.second);
return;
}
}
}
int main()
{
cin >> v >> e;
int x, y, w;
for(int i = 0; i < e; i++) {
cin >> x >> y >> w;
edge[x].push_back(make_pair(w, y));
edge[y].push_back(make_pair(w, x));
}
Prim(1);
cout << sum;
return 0;
}