BOJ
BOJ::1197 최소 스패닝 트리
BOJ Gold 4
BOJ::1197 최소 스패닝 트리
[BOJ] : https://www.acmicpc.net/problem/1197
- Level : Gold 4
시사점
- 최소 스패닝 트리에 대한 기본 문제입니다.
- 프림과 크루스칼의 개념을 까먹으려 할때마다 다시 푸는 문제입니다.
이해(x)
설계(x)
- 프림 : 정점 중심 탐색
- vector<pair<int,int> > adj[MAX_N]; // adj[u] = {v, cost} 를 생성합니다.
- 정점 하나(u)를 방문합니다.
- priority_queue<pair<int,int> > pq;// cost(min), v
- adj[u] 하위 노드들 중 방문하지 않은 노드들에 대해 전역변수인 pq에 삽입합니다.
- pq 중 cost가 가장 작은 정점을 선택하여, 해당 정점으로 재귀합니다.
- 이때 cost를 정답에 더합니다.
- 크루스칼 : 간선 중심 탐색
- 전체 간선을 크기 순으로 pq에 넣습니다.
- pq에서 하나씩 꺼내면서 아래 항목들을 진행합니다.
- cost값을 가진 간선의 양측 정점인 u와 v를 하나의 tree로 merge합니다.
- (하나의 트리가 아니었던 경우(find를 통해 부모 확인))
- merge가 된 경우 해당 cost를 전체 정답에 더합니다.
- cost값을 가진 간선의 양측 정점인 u와 v를 하나의 tree로 merge합니다.
시간 복잡도
공간 복잡도
구현(프림)
// prim
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAX_N = 10000 + 1;
int ans;
int V, E;
bool visited[MAX_N];
vector<pair<int, int> > adj[MAX_N]; // adj[u] = {v, cost}
priority_queue<pair<int, int> > pq; // cost(min), index // pq가 전역으로 있다!!
void prim(int u){
visited[u] = true;
for (int i = 0; i < adj[u].size(); i++){
int there = adj[u][i].first, cost = adj[u][i].second;
if (visited[there] == false){
pq.push({ -cost, there });
}
}
while (!pq.empty()){
int cost = -pq.top().first, there = pq.top().second; pq.pop();
if (visited[there] == false){
ans += cost;
prim(there);
return; // return 해 줘야한다!
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> V >> E;
for (int i = 0; i < E; i++){
int x, y, c;
cin >> x >> y >> c;
adj[x].push_back({ y, c });
adj[y].push_back({ x, c });
}
prim(1);
cout << ans << endl;
return 0;
}
구현(크루스칼)
// Kruscal
#include<iostream>
#include<queue>
using namespace std;
struct edge{
int cost;
int u;
int v;
bool operator <(const edge& t)const{
return cost < t.cost;
}
};
const int MAX_N = 10000 + 1;
int parent[MAX_N];
int find(int u){
if (parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
void merge(int u, int v){
u = find(u); v = find(v);
if (u == v) return;
parent[u] = v;
}
int V, E;
priority_queue<edge> edges; // cost(low), u, v
void Kruscal(){
int ret = 0;
while (!edges.empty()){
int u = edges.top().u, v = edges.top().v, cost = -edges.top().cost; edges.pop();
if (find(u) == find(v)) continue;
merge(u, v);
ret += cost;
}
cout << ret << endl;
}
int main(){
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> V >> E;
for (int i = 0; i < E; i++){
int x, y, c;
cin >> x >> y >> c;
edges.push({ -c, x, y });
}
for (int i = 0; i < V; i++)
parent[i] = i;
Kruscal();
return 0;
}