[c++] 원더랜드(Kruskal MST, Prim MST 알고리즘)

원더랜드(Kruskal MST 알고리즘: Union&Find 활용)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int unf[1001];
struct Edge{
	int v1;
	int v2;
	int val;
	Edge(int a, int b, int c){
		v1=a;
		v2=b;
		val=c;
	}
	bool operator<(Edge &b){
		return val<b.val;
	}
};
int Find(int v){
	if(v==unf[v]) {
		return v;
	}
	else {
		return unf[v]=Find(unf[v]);	
	}
}
void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if(a!=b) unf[a]=b;
}
int main() {
	int i, res=0;
	vector<Edge> Ed;
	//freopen("input.txt", "rt", stdin);
	int n, m, d, a ,b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		unf[i]=i;
	}
	for(i=0; i<m; i++){
		scanf("%d %d %d", &a, &b, &c);
		Ed.push_back(Edge(a, b, c));
	}
	sort(Ed.begin(), Ed.end());
	for(i=0; i<m; i++){
		int fa=Find(Ed[i].v1);
		int fb=Find(Ed[i].v2);
		if(fa!=fb){
			res+=Ed[i].val;
			Union(Ed[i].v1, Ed[i].v2);
		}
	}
	printf("%d ", res);
	return 0;
}

입력값

9 12

1 2 12

1 9 25

2 3 10

2 8 17

2 9 8

3 4 18

3 7 55

4 5 44

5 6 60

5 7 38

7 8 35

8 9 15

 

출력값

196

 

Union&Find를 활용해서 풀었다. 

먼저 Edge구조체에 입력을 도시(a, b)와 도로에 대한 정보(도로를 유지보수하는 비용)를 받고 벡터에 저장한다.

다음으로 도로를 유지보수하는 비용이 작은 Edge부터 앞에 오도록 정렬한다. 

벡터에 정렬된 순으로 Union과 Find를 하면서 도시간에 연결되도록 만들어준다.

경로를 추가했을 떄 순회되도록 경로가 설정되는 경우 그 경로는 추가하지 않는다. 그 경로를 추가할 경우 유지보수하는 비용이 불필요하게 더 추가되기 때문이다.

 

처음에는 이문제를 보면서 작은 값과 비교하면서 넣는 방법으로 접근했는데 

처음부터 Edge로 받아서 그 구조체에서 operator를 오버라이딩해서 유지비용에 따라 먼저 정렬해주고나서 비용이 적은 도시부터 Union&Find해주면 되었다.

 

원더랜드(Prim MST 알고리즘: priority_queue 활용)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int unf[1001], ch[100];
struct Edge{
	int e;
	int val;
	Edge(int a, int b){
		e=a;
		val=b;
	}
	bool operator<(const Edge &b)const{
		return val>b.val;
	}
};
int main() {
	//freopen("input.txt", "rt", stdin);
	priority_queue<Edge> Q;
	vector<pair<int, int> > map[30];
	int i, res=0, n, m, d, a ,b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		map[a].push_back(make_pair(b, c));
		map[b].push_back(make_pair(a, c));
	}
	Q.push(Edge(1, 0));
	while(!Q.empty()){
		Edge tmp=Q.top();
		Q.pop();
		int v=tmp.e;
		int cost=tmp.val;
		if(ch[v]==0){
			res+=cost;
			ch[v]=1;
			for(i=0; i<map[v].size(); i++){
				Q.push(Edge(map[v][i].first, map[v][i].second));
			}
		}
	}
	printf("%d ", res);
	return 0;
}

입력값

9 12

1 2 12

1 9 25

2 3 10

2 8 17

2 9 8

3 4 18

3 7 55

4 5 44

5 6 60

5 7 38

7 8 35

8 9 15

 

출력값

196

 

이전 문제와 같은 문제이며 푸는방법만 다르다.

이전 문제는 경로의 최소비용이 작은것부터 vector<Edge>를 정렬하고 Union&Find를 통해 경로를 합쳐주었다면

본 문제는 vector의 pair에 도시간의 정보와 경로의 비용을 저장해준다.

Edge(1, 0)을 통해 1번 도시부터 시작하며 map[1][i]를 통해 1과 연결된 도시를 한번씩 순회하며 경로의 유지비용이 작은 도시부터 순회한다. 

map[1][0]은 2번도시로 가는 정보, map[1][1]은 9번도시로 가는 정보를

각각 담고 있으므로 그 중 도로의 유지보수 비용이 가장 작은 도로를 priority queue에 넣어준다. 넣어준 도시까지 가는 비용을 res에 합쳐주면 경로를 한번 이어주는 과정이 끝이난다.

 

이제 다시 priority queue에 넣어준 도시의 번호에 연결된 도시와 연결된 곳을 다시 순회하며 유지보수 비용이 작은 도시를 선택하여 경로를 이어주는 방식으로 진행된다.

priority queue에서 top()하였을 때 경로의 비용이 작은 Edge가 도출되는 이유는 operator메소드를 오버라이딩하여 

작은 값부터 출력되도록 하였기 때문이다.