우주신과의 교감
문제 해석
모든 정점을 연결하기 위해 필요한 최소 간선길이를 구하는 문제입니다.
이미 연결된 간선이 있고, 나머지 연결이 안된 정점들을 모두 연결해주어야 합니다.
설계(10)
모든 정점을 최소 간선가중치로 연결하는 최소 스패닝 트리를 구현하는 문제로 보입니다.
사용할 수 있는 알고리즘은 크루스칼, 프림 알고리즘이 있고 저는 크루스칼 알고리즘을 사용하겠습니다.
기존의 알고리즘과 다른 점은 이미 연결되어있는 간선이 있다는 것입니다. 이미 연결된 부분을 미리 union-find 기법으로 연결해줍니다.
연결된 정점을 제외한 모든 정점간의 간선을 만들어서 가중치가 작은 순으로 정렬 후, merge를 시켜줍니다.
여기서 주의할점은 자료형 체크를 잘 해주어야 합니다. 각 좌표가 최대 10^6이므로 거리를 구해줄 때 제곱을 하면서 int형으로는 오버플로우가 날 것이기 때문에 안전하게 long long자료형을 선정하였습니다.
크루스칼 알고리즘을 사용하였고, 경로압축기법을 사용하였기 때문에 에크만 함수에 의해 Merge부분이 O(1)이 되면서 O(N^2)의 시간복잡도가 나오므로 정렬알고리즘에 의해 전체 시간복잡도가 O(N^2logN^2)으로 정해집니다.
구현(20)
코드
#include <iostream>
#include <math.h>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;
#define MAXN 1001
#define ll long long
int par[MAXN],N,M;
bool visited[MAXN][MAXN];
double ans;
struct node {
int u, v;
double dist;
bool operator < (const node& a) const {
return dist < a.dist;
}
};
vector<node> vt,tmp;
pair<ll, ll> coord[MAXN];
ll square(ll x) {
return x * x;
}
double calc_dist(int u, int v) {
return sqrt(square(coord[u].first - coord[v].first) + square(coord[u].second - coord[v].second));
}
int Find(int x) {
if (par[x] == -1) return x;
return par[x] = Find(par[x]);
}
void Merge(int u, int v,double dist) {
u = Find(u);
v = Find(v);
if (u == v) return;
par[u] = v;
ans += dist;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
memset(par, -1, sizeof(par));
cin >> N >> M;
for (int i = 1; i <= N; i++) {
ll x, y;
cin >> x >> y;
coord[i] = { x,y };
}
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
visited[u][v] = true;
visited[v][u] = true;
double tmp_dist = calc_dist(u, v);
vt.push_back({ u,v,tmp_dist });
Merge(u, v, tmp_dist);
}
ans = 0.0;
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
if (visited[i][j]) continue;
tmp.push_back({ i,j,calc_dist(i,j) });
}
}
if (tmp.size()) sort(tmp.begin(), tmp.end());
for (int i = 0; i < tmp.size(); i++) {
Merge(tmp[i].u, tmp[i].v,tmp[i].dist);
}
printf("%.2f", ans);
return 0;
}
디버깅
거리를 계산할 때, 오버플로우가 나올 것을 처음에 생각하지 못했습니다. 다시 한번 눈으로 디버깅을 할 때 알아차리고 바로 변경하였습니다.
제출결과
32 ms
마무리
기본 알고리즘만 알고있으면 쉽게 풀이 가능한 문제인 것 같습니다.