[BOJ] 1197 최소 스패닝 트리

 

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

알고리즘: MST(Kruskal, Prim)

 

시간복잡도: O(E*logV)

 

---

 

1. Kruskal (간선 기준): 가중치가 최소인 간선부터 하나씩 선택해가면서 같은 트리에 속해있는지 확인.

                             같은 트리인지 확인하는건 Union-Find 알고리즘 이용

 

2. Prim (정점 기준):  정점 기준으로 BFS 돌리기 (가장 작은 가중치를 가진 간선 선택)

                           priority-queue를 이용. (가중치 기준 정렬)

 

/* 1197: 최소 스패닝 트리
 * Kruskal
**/

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

int V, E;
vector<int> p, r;	// parent, rank
long long int sum;

struct e
{
	int a, b, c;
}t;

bool cmp(const e &x, const e &y)
{
	return x.c < y.c;
}

// Union-Find
int findParent(int s)
{
	if (p[s] == s) return s;
	return p[s] = findParent(p[s]);
}
bool unionSet(int x, int y)
{
	x = findParent(x);
	y = findParent(y);
	if (x == y) return 0;
	if (r[x] > r[y])
		p[y] = x;
	else
		p[x] = y;
	if (r[x] == r[y]) 
		++r[y];
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> V >> E;
	
	vector<e> G(E);
	for (int i = 0; i < E; ++i)
	{
		cin >> t.a >> t.b >> t.c;
		G[i] = t;
	}
	sort(G.begin(), G.end(), cmp);
	
	for (int i = 0; i < V; ++i)
	{
		p.push_back(i);
		r.push_back(0);
	}
	
	for (e i : G)
	{
		if(unionSet(i.a, i.b))
			sum += i.c;
	}
	
	cout << sum;
	return 0;
}

 

/* 1197: 최소 스패닝 트리
 * Prim
**/

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
typedef pair<int, int> ii;

int V, E, a, b, c;
long long int sum;
ii h;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> V >> E;
	
	vector<ii> G[V];
	vector<int> chk(V, 0);
	priority_queue<ii, vector<ii>, greater<ii> > pq; 
	
	for (int i = 0; i < E; ++i)
	{
		cin >> a >> b >> c;
		G[a-1].push_back({c, b-1});
		G[b-1].push_back({c, a-1});
	}
	pq.push({0, 0});
	
	while(!pq.empty())
	{
		h = pq.top();
		pq.pop();
		if (chk[h.second])
			continue;
		chk[h.second] = 1;
		sum += h.first;
		
		for (ii i : G[h.second])
		{
			if (!chk[i.second])
				pq.push(i);
		}
	}
	
	cout << sum;
	return 0;
}

 

 

 

 

---

 

참고) 실전에는 Kruskal이 MST 응용문제를 푸는데 더 유용한 경우가 많음. (코드가 더 깔끔)

 

예제)

1. K 개의 간선으로 이루어진 MST 구하기 (Union-Find 성질 이용)

https://www.acmicpc.net/problem/4343

4343번: Arctic Network

 

 

2. 두번째로 작은 MST 구하기 (LCA 이용)

https://www.acmicpc.net/problem/1626

1626번: 두 번째로 작은 스패닝 트리