최소 신장 트리 (Minimun Spanning Tree) MST, swexpert 1251 하나로
최소 신장 트리 MST
Spanning Tree 는 연결 Graph 이자, 무향그래프의 SubGraph 로 모든 정점을 포함하고 사이클이 없는 그래프를 뜻합니다.
Spanning Tree 중 간선의 가중치의 합이 최소인 것을 MST 라고 합니다.
MST 를 찾아내는 방법은
1. 프림 알고리즘 (Prim's Algorithm)
2. 크루스칼 알고리즘 (Kruskal's Algorithm)
이 있습니다.
프림 알고리즘 (Prim's Algorithm)
- Dense 한 그래프에서 MST를 찾을때 좋은 알고리즘으로 시간복잡도는 PQ의 구현에 따라 달라집니다.
PQ를 Heap으로 구현하였을 때, O(ElogV) 의 시간 복잡도를 가질 수 있습니다.
(a) 초기 가중치가 있는 무향 그래프 입니다.
(b) 시작 정점을 선택합니다. -> 시작 정점은 아무 정점을 선택할 수 있습니다.
(c) A 정점에서 연결된 간선 중 가장 가중치가 작은 간선을 선택합니다. -> 이 부분을 PQ를 이용하여 빠르게 찾아낼 수 있습니다.
(d) 가장 가중치가 작은 간선을 선택한 후, 연결된 정점을 Tree Set에 추가시켜 줍니다. 뿐만아니라 추가된 정점에 연결된 간선을 PQ에 추가시켜 줍니다.
(e-f) 이후 이 과정을 반복하여 MST를 찾을 수 있습니다. 만약 이미 Tree Set에 추가된 정점이라면 Cycle이 생기기 때문에 연결하지 않습니다.
크루스칼 알고리즘 (Kruskal's Algorithm)
- Spase 한 그래프에서 MST를 찾을 때, 좋은 알고리즘으로 O(ElogE) 의 시간복잡도를 가집니다.
- 많은 사람들이 사용하고 있는 Union-Find 알고리즘을 사용하여 크루스칼 알고리즘을 구현할 수 있습니다.
모든 Vertex를 Tree라고 하고, 모든 Edge 중에 가장 작은 Edge를 선택합니다.
만약 두 Vertex가 같은 Tree라면 Cycle이 생기기 때문에 선택하지 않고, 다른 트리라면 선택하여 Union을 해줄 수 있습니다.
1. 
3.
5.
1) 모든 정점을 TreeSet으로 설정합니다.
2) 모든 정점을 PQ에 넣어 가중치가 작은 순으로 정렬합니다.
3) 가중치가 가장 작은 간선의 양 끝 정점을 연결하여 TreeSet을 만들어줍니다.
4~5) 이와 같은 과정을 반복합니다. 만약 같은 Tree Set에 추가된 정점이라면 Cycle이 생기기 때문에 연결하지 않습니다.
6) 마지막으로 완성된 MST에 연결된 간선의 정보입니다.
SWEXPERT 1251_ 하나로 를 MST를 이용하여 해결 할 수 있습니다. 크루스칼 알고리즘을 사용하여 문제를 해결하였습니다.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int n;
double e;
long long arr[1010][1010];
long long parents[1010];
long long find(long long first) {
if(parents[first] == first) {
return first;
}
else {
return parents[first] = find(parents[first]);
}
}
bool Union(long long first, long long second) {
long long pF = find(first);
long long pS = find(second);
if(pF == pS)
return true;
parents[pF] = pS;
return false;
}
int main() {
int t;
scanf("%d",&t);
for(int test = 1; test <= t; test++) {
priority_queue<pair<long long, pair<long long ,long long>>> pq;
memset(arr, 0, sizeof(arr));
memset(parents, 0, sizeof(parents));
scanf("%d",&n);
vector<long long>x,y;
x.resize(n);
y.resize(n);
for(int i=0;i<n;i++) {
scanf("%lld",&x[i]);
}
for(int i=0;i<n;i++) {
scanf("%lld",&y[i]);
}
scanf("%lf",&e);
for(long long i=0;i<n;i++)
parents[i] = i;
for(long long i=0;i<n;i++) {
for(long long j=i+1;j<n;j++) {
arr[i][j] = ((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]));
arr[j][i] = arr[i][j];
pq.push(make_pair(-arr[i][j],make_pair(i,j)));
}
}
double size = 0;
int cnt = 0;
while(!pq.empty()) {
if(cnt == n-1)
break;
long long dist = -pq.top().first;
long long first = pq.top().second.first;
long long second = pq.top().second.second;
pq.pop();
bool isUnion = Union(first, second);
if(isUnion)
continue;
size += dist;
cnt++;
}
size = (size * e);
printf("#%d %0.lf\n",test, size);
}
}