(C++) - 백준(BOJ) 1774번 : 우주신과의 교감

https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

크루스칼 문제였습니다.

 

 

 

📕 풀이방법

 1. 입력, 초기화

  1-1. n만큼 좌표를 입력받습니다. 

  1-2. m만큼 이미 연결된 통로를 입력 받습니다. 이미 연결되어 있는 간선들은 트리형태로 구성되어 있습니다. 따라서 parent 배열을 이용해 union를 한다면 독립된 트리들이 한 개 혹은 여러개로 구성됩니다. 

 

 2. 서로 연결이 될 수 있는 후보간선들을 edges라는 변수에 모두 넣습니다. 후보간선이란 이미 연결된 간선을 제외한 나머지를 의미하며 정점끼리 연결할 수 있는 간선들을 의미합니다. 후보간선인지 아닌지는 find함수를 통해 알 수 있습니다. 서로 다른 tree라면 각자의 parent가 가르키는 node가 다릅니다. 후보간선 정보를 담고 있는 변수인 edges는 두 정점과 그 사이의 거리가 저장됩니다.

 

 3. 후보간선들을 거리의 오름차순으로 정렬합니다.

 

 4. 후보간선들을 사이클이 발생하지 않도록 적절히 뽑습니다. 최소거리들로 이미 정렬되어 있으므로 연결시 사이클이 발생하지 않는다면 find의 반환값이 다를 것입니다. 이 경우에 union해주고 그 사이의 거리를 ans변수에 더함으로써 mst를 구할 수 있습니다.

 

* 반드시 소수셋째자리에서 반올림해야합니다. %.2f를 이용하면 쉽게 반올림하여 출력할 수 있습니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m, parent[1001];
double ans;
struct Edge { int u, v; double w; };
vector <Edge> edges;
vector <pii> coords;

double getDistance(int x1, int y1, int x2, int y2){
    double X = abs(x1 - x2);
    double Y = abs(y1 - y2);
    return sqrt(abs(X*X+Y*Y));
}

bool cmp(Edge &a, Edge &b){
    return a.w < b.w;
}

int find(int x){
    if(x == parent[x]) return x;
    return parent[x] = find(parent[x]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    parent[a] = b;
}

int main(){
    cin >> n >> m;
    coords.resize(n + 1);
    for(int i = 1; i <= n; i++) parent[i] = i;
    
    for(int i = 1,x,y; i <= n; i++){
        cin >> x >> y;
        coords[i] = {x,y};
    }

    for(int i = 1,x,y; i <= m; i++){
        cin >> x >> y;
        if(find(x) != find(y)){
            merge(x,y);
        }
    }


    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(find(i) != find(j)){
                int x1 = coords[i].first;
                int y1 = coords[i].second;
                int x2 = coords[j].first;
                int y2 = coords[j].second;
                edges.push_back({i,j, getDistance(x1,y1,x2,y2)});
            }
        }
    }

    sort(edges.begin(),edges.end(),cmp);

    for(int i = 0; i < edges.size(); i++){
        if(find(edges[i].u) != find(edges[i].v)){
            merge(edges[i].u,edges[i].v);
            ans += edges[i].w;
        }
    }
    
    printf("%.2f",ans);
}

 

---

📕 Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

4 2
0 0
0 1
0 2
0 3
1 4
2 3

답

1.00