BOJ - 1197번 최소 스패닝 트리 (C++)

문제 출처: https://www.acmicpc.net/problem/1197

문제 접근법

MST : 최소 신장 트리로 사이클이 없으며 모든 정점이 연결 된 상태에서 최소 가중치 합을 말한다.
이 구현 방법에는 두가지가 있는데 Kruskal과 Prime 알고리즘이다.
이 문제에서 두 개를 모두 구현해볼 것이다.

통과 코드

크루스칼
1) 그래프 간선들의 가중치들을 오름차순으로 정리한다.
2) 정렬된 간선 리스트에서 선택되지 않는 간선을 선택한다.
(단, 사이클을 형성하는 간선은 제외)
3) 현재 간선을 MST 집합에 추가한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


struct Data {
	int v, e, m;
	Data(int ve, int end, int money) {
		v = ve;
		e = end;
		m = money;
	}
	bool operator<(Data &d) {
		return m < d.m;
	}
};

int res;
int arr[10001];

int Find(int v) {
	if (v == arr[v]) return v;
	else return arr[v] = Find(arr[v]);
}

void Union(int a, int b, int c) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		arr[a] = b;
		res += c;
	}
}

int main() {
	int  V, E;
	cin >> V >> E;
	for (int i = 1; i <= V; i++) {
		arr[i] = i;
	}
	vector<Data> a;
	for (int i = 0; i < E; i++) {
		int e, b, c;
		cin >> e >> b >> c;
		a.push_back(Data(e, b, c));
	}
	sort(a.begin(), a.end());
	for (int i = 0; i < a.size(); i++) {
		Union(a[i].v, a[i].e, a[i].m);
	}
	cout << res << "\n";

	return 0;
}

프림

1) 시작 단계에서는 시작 정점만이 MST 집합에 포함된다.
2) 인접 정점들 중에 최소 가중치를 가진 간선을 선택해 트리를 추가한다.
3) 위의 과정을 트리가 N-1개 간선을 가질 때까지 반복한다.

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

using namespace std;


struct Data {
	int e, m;
	Data(int edge, int money) {
		e = edge;
		m = money;
	}
	bool operator<(const Data &d)const {
		return m > d.m;
	}
};

vector<Data> arr[10001];
bool ch[10001];

int main() {
	int  V, E,res=0;
	cin >> V >> E;
	vector<Data> a;
	for (int i = 0; i < E; i++) {
		int e, b, c;
		cin >> e >> b >> c;
		arr[e].push_back(Data(b, c));
		arr[b].push_back(Data(e, c));
	}
	priority_queue<Data> pq;
	pq.push(Data(1, 0));
	while (!pq.empty()) {
		int v = pq.top().e;
		int c = pq.top().m;
		pq.pop();
		if (ch[v]) continue;
		ch[v] = true;
		res += c;
		for (int i = 0; i < arr[v].size(); i++) {
			pq.push(arr[v][i]);
		}
	}
	cout << res << "\n";

	return 0;
}