MST(Minimum Spanning Tree) 최소 스패닝 트리 + 백준 문제 추천
사용언어
Visual studio 2019 C++
MST(Minimum Spanning Tree)
Spanning Tree 중에서 간선들의 cost 합이 최소인 트리
- N개의 정점에는 N-1개의 간선이 필요하다.
- 사이클이 존재하면 안된다.
풀이
보통 우선순위 큐를 사용해서 많이 푼다.
예시와 함께 설명해보도록 하겠다.
1647 도시 분할 계획
이 문제의 input값은 보다시피 N개의 정점 M개의 간선으로 볼 수 있다.
input코드이다.
int N, M;
vector<pair<int, int>> v[MAX];
void input() {
cin >> N >> M;
int a, b, cost; // 정점 a,b & 가중치 cost
for (int i = 0; i < M; i++) {
cin >> a >> b >> cost;
v[a].push_back(make_pair(b, cost));
v[b].push_back(make_pair(a, cost));
}
}
이제 인접한 정점들 중 N-1개의 간선으로, 최소의 cost값을 사용하는 MST를 살펴보자.
bool visited[MAX];
int city(int start) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
visited[start] = true;
for (int i = 0; i < v[start].size(); i++) {
int cur = v[start][i].first;
int cost = v[start][i].second;
pq.push(make_pair(cost, cur));
}
int max_cost = 0;
int result = 0;
while (!pq.empty()) {
int cost = pq.top().first;
int cur = pq.top().second;
pq.pop();
if (visited[cur])
continue;
visited[cur] = true;
result += cost;
max_cost = max(max_cost, cost);
for (int i = 0; i < v[cur].size(); i++) {
int next = v[cur][i].first;
int n_cost = v[cur][i].second;
pq.push(make_pair(n_cost, next));
}
}
return result - max_cost;
}
또한 이 문제가 다른 스패닝트리와 다른점은 두 마을로 나누는 최소값이므로 가장 큰 cost값을 result값에서 빼줘야 한다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl "\n"
#define MAX 100001
using namespace std;
int N, M;
bool visited[MAX];
vector<pair<int, int>> v[MAX];
void init() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int city(int start) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
visited[start] = true;
for (int i = 0; i < v[start].size(); i++) {
int cur = v[start][i].first;
int cost = v[start][i].second;
pq.push(make_pair(cost, cur));
}
int max_cost = 0;
int result = 0;
while (!pq.empty()) {
int cost = pq.top().first;
int cur = pq.top().second;
pq.pop();
if (visited[cur])
continue;
visited[cur] = true;
result += cost;
max_cost = max(max_cost, cost);
for (int i = 0; i < v[cur].size(); i++) {
int next = v[cur][i].first;
int n_cost = v[cur][i].second;
pq.push(make_pair(n_cost, next));
}
}
return result - max_cost;
}
void input() {
cin >> N >> M;
int a, b, cost;
for (int i = 0; i < M; i++) {
cin >> a >> b >> cost;
v[a].push_back(make_pair(b, cost));
v[b].push_back(make_pair(a, cost));
}
}
int main() {
init();
input();
cout << city(1) << endl;
}
위의 풀이를 이해했다면 밑의 문제는 푸는 방식이 똑같아서 쉽다.
Comments