(BOJ) 1774 우주신과의 교감

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

 

문제풀이:

거리를 모두 구해서 priority_queue에 넣음

mst 사용

 

주의1. double을 사용해야 한다.

while문에서 cost를 int형으로 선언한걸 못 찾아서 계속 맞왜틀.... ㅠㅠ 하다가 겨우겨우 맞음

 

주의2. 미리 연결된 통로들이 항상 mst로 연결되었음을 보장할 수 없다.

즉, while문에서 if(cnt==n-m) break; 이런식으로 풀면 틀림

 

priority_queue 사용하는 것보다 vector에 거리 차 다 넣어 놓고 sorting 해서 풀면 시간이 절반으로 줄어든다.

	sort(pq.begin(), pq.end());
	for(int i=0;i<pq.size();i++){
		double cost = pq[i].first;
		int a = pq[i].second.first;
		int b = pq[i].second.second;

		if (merge(a, b)) {
			cnt++;
			res += cost;
			if (cnt == n - 1) break;
		}
	}

이름만 pq임 vector로 받아온 것 sort해서 merge한 것

둘 다 sorting 하는데 NlogN 걸리는데 priority_queue는 pop하면 down heap하는데 logN 걸려서 그런가 봄 

 

 

소스 코드:

그냥 priority_queue 사용한 것 

int n, m, p[1001],cnt;
double res;
typedef pair<double,pair<int, int>> P;
vector<pair<int, int>> v;
priority_queue<P, vector<P>, greater<P>> pq;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	p[a] = b;
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);


	cin >> n >> m;
	memset(p, -1, sizeof(p));
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back({ a,b });
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			double t = sqrt(pow(v[i].first - v[j].first, 2)+pow(v[i].second-v[j].second,2));
			pq.push({ t,{i,j} });
		}
	}
	for (int j = 0; j < m; j++) {
		cin >> a >> b;
		merge(a - 1, b - 1);
	}
	while (!pq.empty()) {
		double cost = pq.top().first;
		int a = pq.top().second.first;
		int b = pq.top().second.second;
		pq.pop();

		if (merge(a, b)) {
			cnt++;
			res += cost;
			if (cnt == n - 1) break;
		}
	}
	cout <<fixed<<setprecision(2)<< res << '\n';
	return 0;
}