(백준 알고리즘 문제풀이) 1774번 우주신과의 교감
by 줌코딩
문제
문제 접근
- 이 문제는 모든 노드가 연결되는 최소 엣지를 찾는 MST를 구하는 문제이다.
- 여기서 문제는 가장 짧은 거리를 구해야한다는 것이다.
- 이를 위해서 priority queue를 이용해서 미리 거리를 다 구해놓고 하나씩 연결해가면서 싸이클이 발생하는지 확인하는 과정을 진행하였다.
코드
#include <cstdio>
#include <queue>
#include <cmath>
#define pii pair<int, int>
#define pdp pair<double, pii>
using namespace std;
int n, m, v1, v2, par[1002], X[1002], Y[1002];
double sqr(double d){return d*d;}
int find(int x){
if(par[x] == x)return x;
return par[x] = find(par[x]);
}
int Union(int x, int y){
int px = find(x), py = find(y);
if(px == py)return 0;
par[px] = py;
return 1;
}
int main(){
double ans = 0;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d %d", &X[i], &Y[i]);
par[i] = i;
}
for(int i = 0; i < m; i++){
scanf("%d %d", &v1, &v2);
Union(v1, v2);
}
priority_queue<pdp> pq;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
double d = sqr(X[i] - X[j]) + sqr(Y[i] - Y[j]);
pq.push(pdp(-d, pii(i, j)));
}
}
int cnt = m;
while(!pq.empty() && cnt != n - 1){
pdp top = pq.top(); pq.pop();
double tv = top.first;
int tx = top.second.first, ty = top.second.second;
if(Union(tx, ty))ans += sqrt(-tv), cnt++;
}
printf("%.2f", ans);
}
느낀점
- 타입을 float으로 하니까 100000*100000의 값을 이상하게 담아내는 것을 확인할 수 있었다.
- 필요한 변수형이 뭔지 확인하고 문제를 풀도록 하자.
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
Subscribe via RSS