[C++]백준 1774번 : 우주신과의 교감

www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

1. 접근

크루스칼 알고리즘으로 입력이 조금 특이해서 2가지 처리를 해서 기반을 만들어주어야 한다.

1) 이미 연결되어 있는 edge 정보를 저장

2) 좌표만 주어지기 때문에 각각의 좌표 간 거리 정보를 구해서 저장

 

2. 개선

edge의 최소 거리 순으로 MST를 찾아야하기 때문에 관성적으로 pq를 썼는데

그냥 edge를 기본 배열에 넣고 처음에 오름차순으로 정렬 후 순차적으로 탐색하는 것이 2배 빨랐다.

그리고 거리 정보에 대해 double 타입을 사용해야한다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <cmath>

using namespace std;

struct state{
	int a, b;
	double c;
};

double ans = 0;

int N, M, x, y;
vector<pair<int, int>> v;
vector<state> e;
int res = 0;
int p[1001];

bool cmp(state a, state b){
	return a.c < b.c;
}

double dist(int x, int y){
	return (double)sqrt(pow(abs(v[x].first - v[y].first), 2) + pow(abs(v[x].second - v[y].second), 2));
}

int find(int n){
	if (p[n] == n) return n;
	return p[n] = find(p[n]);
}

bool union_node(int x, int y){
	int px = find(x), py = find(y);

	if (px == py)
		return false;

	p[max(px, py)] = min(px, py);
	
	return true;
}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); 
	cout << fixed;
	cout.precision(2);

	
	cin >> N >> M;
	for (int i = 0; i <= N; i++)
		p[i] = i;

	// 좌표 입력
	for (int i = 0; i < N; i++){
		cin >> x >> y;
		v.push_back({ x, y });
	}
	// 이미 있는 통로
	for (int i = 0; i < M; i++){
		cin >> x >> y;
		union_node(x, y);
	}
	// 좌표 간 만들 수 있는 통로 저장
	for (int i = 0; i < N - 1; i++){
		for (int j = i + 1; j < N; j++){
			e.push_back({ i + 1, j + 1, dist(i, j) });
		}
	}

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

	// MST
	for (int i = 0; i < e.size();i++){
		if (union_node(e[i].a, e[i].b)){
			res++;
			ans += e[i].c;
		}
	}

	cout << ans;

	return 0;
}