문제

문제 링크

어떻게 접근할 것인가?

  • 이것은 Minimum Spanning Tree의 문제이다.
  • Minimum Spanning Tree를 위한 크루스칼 알고리즘을 공부해놨던 것을 참고 했다.
  • 먼저 각 좌표를 다 받고 edge를 생성해놨다.
  • edge를 sorting하고 하나씩 추가해가면서 cycle 여부를 확인한다.

MST 정리 자료(크루스칼)

Cycle 여부 확인 방법(Union-Find)

코드

#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <math.h>

using namespace std;

vector<pair<float, float> > v; 
vector<vector<float> > edge;

int* parent;

int find(int i){
    if(parent[i] == -1) return i;
    return find(parent[i]);
}

void Union(int x, int y){
    int xset = find(x);
    int yset = find(y);
    if(xset != yset) parent[xset] = yset; 
}

int isCycle(int src, int dest){
    int x = find(src); 
    int y = find(dest);
    if (x == y) return 1; 
    Union(x, y);  
    return 0; 
}

bool compare(vector<float> a, vector<float> b){
    return a[2] < b[2];
}

float find_d(int i, int j){
    return sqrt(pow((v[i].first - v[j].first), 2) + pow((v[i].second - v[j].second), 2));
}

int main(){
    int n;
    float x, y;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%f %f", &x, &y);
        v.push_back(make_pair(x, y));
    }
    int edge_N = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            float d = find_d(i, j);
            edge.push_back(vector<float>());
            edge[edge_N].push_back(i);
            edge[edge_N].push_back(j);
            edge[edge_N].push_back(d);
            edge_N ++;
        }
    }
    int count = 0;
    parent = new int[n]; 
    for(int i = 0 ; i < n; i++) parent[i] = -1;
    sort(edge.begin(), edge.end(), compare); 

    float answer = 0;
    for(int i = 0; i < edge.size(); i++){
        if(!isCycle((int)edge[i][0], (int)edge[i][1])){
            answer += edge[i][2];
            count ++;
            if(count == n - 1) break;
        }
    }
    printf("%.2f", answer);
    return 0;
}