BOJ 1774 우주신과의 교감

1 개요

BOJ 1774 우주신과의 교감

• 백준 온라인 저지 1774번 문제
• BOJ 37단계

2 C++

#include <bits/stdc++.h>
using namespace std;

struct Loc {
    int x;
    int y;
};
struct Edge {
    int num1;
    int num2;
    double cost;
};
int N, M;
vector<Loc> loc(1001);
vector<pair<int, int>> links(1001);
vector<int> parent(1002);

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

void Union(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if(a != b) parent[a] = b;
}

void solve() {
    vector<Edge> edges;
	for (int i=1; i<=N-1; i++) {
		for (int j=i+1; j<=N; j++) {
		    double dist = sqrt(pow((loc[i].x - loc[j].x), 2) + pow((loc[i].y - loc[j].y), 2));
			edges.push_back({i, j, dist});
		}
	}
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.cost < b.cost;
    });
	for (int i=1; i<=N; i++) {
		parent[i] = i;
	}
	for (int i=0; i<M; i++) {
		Union(links[i].first, links[i].second);
	}
	double answer = 0;
	for (int i=0; i<edges.size(); i++) {
		if (getParent(edges[i].num1) != getParent(edges[i].num2)) {
			Union(edges[i].num1, edges[i].num2);
			answer += edges[i].cost;
		}
	}
	cout << fixed;
	cout.precision(2);
	cout << answer;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i=1; i<=N; i++) {
		cin >> loc[i].x;
		cin >> loc[i].y;
	}
	for (int i=0; i<M; ++i) {
		cin >> links[i].first;
		cin >> links[i].second;
	}
    solve();
}