[1197] 최소 스패닝 트리 - MST(Kruskal,prim) ★☆☆ / 복습 ○

 

 

[ 문제 ] : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

---

 

[ 문제 접근 ]

 

기본 적인 MST ( 미니멈 스패닝 트리 ) 문제.

- Kruskal, Prim 두 가지 방법으로 풀어 보았다.

​

자세한 접근법 : https://forward-movement.tistory.com/23

---

[ Kruskal 코드 ]

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

using std::cout; using std::cin;
using std::vector; using std::pair;

int V, E;
int A, B, C;

class Edge {
public:
	int node[2];
	int cost;
	Edge(int a, int b, int _cost) :cost(_cost) {
		node[0] = a;
		node[1] = b;
	}
	bool operator<(const Edge& e) {
		return cost < e.cost;
	}
};
vector<Edge> edges;
int parent[10001];
int tree_size[10001];

int findSet(int a) {
	if (a != parent[a]) parent[a] = findSet(parent[a]);

	return parent[a];
}

void unionSet(int a,int b) {
	int x = findSet(a);
	int y = findSet(b);
	if (tree_size[x] > tree_size[y]) {
		parent[y] = x;
		tree_size[x] += tree_size[y];
	}
	else {
		parent[x] = y;
		tree_size[y] += tree_size[x];
	}
}
// ## Kruskal
// 0.공집합에서 시작
// 1. make-set 모두 따로 집합으로 만든다. ( 배열로 )
// 2. 엣지들 오름차순 정렬
// 3. n-1이 될때까지 find- union 반복.

int kruskal() {
	int answer = 0;
	for (int i = 1; i <= V; i++) {
		parent[i] = i;
	}
	std::fill_n(tree_size, V + 1, 1);

	std::sort(edges.begin(), edges.end());

	int cnt = 0;
	for (int i = 0; i < edges.size() && cnt < V - 1; i++) {
		int cur = edges[i].node[0];
		int next = edges[i].node[1];
		int cost = edges[i].cost;
		if (findSet(cur) != findSet(next)) {
			unionSet(cur, next);
			answer += cost;
			cnt++;
		}
	}

	return answer;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> V >> E;
	edges.reserve(100001);
	while (E--) {
		cin >> A >> B >> C;
		edges.push_back(Edge(A, B, C));
	}
	cout << kruskal();
	

	return 0;
}

---

[ Prim 풀이 ]

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

constexpr auto INF = 987654321;

using std::cout; using std::cin;
using std::vector; using std::pair;


int V, E;
int A, B, C;
vector<pair<int, int>> edges[10001];
int visited[10001];

template<typename T>
struct cmp {
	bool operator()(const T& a, const T& b)const {
		return a.second > b.second;
	}
};

// ## Prim
// 0. 어디서 시작하는지는 중요하지 않다. 
// 1. 1번에서 시작했다 하면, 1번의 인접한 노드들을 pq에 넣고
// 2. pq.top() 하면 자동으로 cost가 작은 값이 나오고, pq.pop() 해주고
// 3. if (visited = false )인 top()의 인접한 노드 다시 pq에 집어넣는다.
// 4. 큐가 비거나 선택한 엣지의 개수가 N-1개가 될때까지 반복한다.
int prim(int start) {
	int answer = 0;
	std::priority_queue<std::pair<int, int>, vector<std::pair<int, int>>, cmp<std::pair<int,int>>> pq;
	visited[1] = true;
	for (int i = 0; i < edges[1].size(); i++) {
		int x = edges[1][i].first;
		int y = edges[1][i].second;
		pq.push({ x,y });
	}
	int cnt = 0;
	while (!pq.empty() && cnt < V-1) {
		int cur = pq.top().first;
		int cur_cost = pq.top().second;
		pq.pop();
		
		if (!visited[cur]) {
			visited[cur] = true;
			answer += cur_cost;
			cnt++;
			for (size_t i = 0; i < edges[cur].size(); i++) {
				int next = edges[cur][i].first;
				int next_cost = edges[cur][i].second;
				if (visited[next]) continue;
				pq.push({ next,next_cost });
			}
		}
	}

	return answer;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> V >> E;
	
	while (E--) {
		cin >> A >> B >> C;
		edges[A].push_back({ B,C });
		edges[B].push_back({ A,C });
	}
	cout << prim(1);
	

	return 0;
}

---