최소 신장 트리 (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. 2.  

3.4.  

5.6. 

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);
        
    }
    
}