[Algospot] 알고스팟 LAN 근거리 네트워크

출처:  https://algospot.com/judge/problem/read/LAN

 Input 

2

3 1

0 0 1

0 1 2

0 1

10 5

-7 -7 10 -4 10 -4 -5 0 -10 -6

6 8 -5 3 -4 6 -10 4 -7 10

9 7

7 3

9 7

5 0

8 6

 

 Output 

1.4142135624

29.7042202421

 

크루스칼 알고리즘 이용.

▷ (1, 2)와 연결되어 있지 않았으므로 다른 정점에서 연결해야 합니다.

▷ (0, 1)과 (1, 2)가 최소거리 이므로 연결해줍니다.

▷ Math.sqrt((1-0)2 + (2-1)2) = 1.4142135624

 

모든 간선이 최소 비용으로 연결해야 하는 [BOJ] 1197 최소 스패닝 트리 문제입니다.

[BOJ] 백준 1197 최소 스패닝 트리

프림 알고리즘, 크루스칼 알고리즘 중 크루스칼 알고리즘 이용.

- 각 정점별 거리로 가중치를 구합니다.

※ 유사문제 풀이: [BOJ] 1922 네트워크 연결 

[BOJ] 백준 1922 네트워크 연결

---

#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;
 
#define PAIR pair<double,pair<int,int> >
int N, M;
vector<int> parent;
vector<pair<int, int> > point;
 
double findDistance(int u, int v){
    int dx = point[u].first - point[v].first;
    int dy = point[u].second - point[v].second;
    return sqrt((dx*dx) + (dy*dy));
}
 
int find(int v){
    if (v == parent[v]){
        return v;
    } 
    else{
        return parent[v] = find(parent[v]);
    }
}
 
void merge(int u, int v){
    u = find(u);
    v = find(v);
    if (u == v) return;
    parent[u] = v;
}
int main(){
    int test_case;
    cin >> test_case;
 
    while (test_case--){
        // 정점과 간선의 개수
        cin >> N >> M;
        
        parent = vector<int>(N);
        point = vector< pair<int, int> >(N);
        priority_queue <PAIR, vector<PAIR>, greater<PAIR> > pq;
        
        // x, y 좌표
        for (int i = 0; i < N; i++) cin >> point[i].first;
        for (int i = 0; i < N; i++) cin >> point[i].second;
        
        for (int i = 0; i < N; i++) parent[i] = i; // union-find 초기화
        for (int i = 0; i < M; i++){
            int u, v;
            cin >> u >> v;
            // 이미 확인된 연결확인한 간선 제외
            if (find(u) != find(v)){
                merge(u, v);
            }
        }
        // 각 좌표간 거리(가중치)를 구해서 우선순위큐 push
        for (int i = 0; i < N; i++){
            for (int j = i + 1; j < N; j++){
                pq.push(make_pair(findDistance(i, j), make_pair(i, j)));
            }
        }
        // 비용이 낮은 간선부터 정점 연결시도
        double result = 0.0;
        while (!pq.empty()){
            double distance = pq.top().first;
            int u = pq.top().second.first;
            int v = pq.top().second.second;
            pq.pop();
            
            // union-find로 사이클 형성 확인시 제외
            if (find(u) != find(v)){
                merge(u, v);
                result += distance;
            }
        }
        
        printf("%0.10f\n", result);
    }
}