[BOJ] 4386번 : 별자리 만들기

https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

 

아주 기초적인 MST 문제다.

 

별자리들의 좌표를 받아서 별들 사이의 거리를 저장해서 prim's algorithm으로 풀든지 kruskal's algorithm으로 풀던지 하면 된다.

 

나는 kruskal's algorithm으로 풀었다. N이 매우 작기 때문에 시간은 크게 고려하지 않아도 된다.

 

time complexity를 따지자면, $O(N^2 \log{N} * \alpha)$ 정도일듯. 두 node가 연결되었는지 확인하는 과정에서 union-find algorithm을 쓰는데 보통 상수 시간이 걸리지만 최악의 경우 N까지 걸릴 수 있기 때문에 $\alpha$라고 써 놨다.

 

다만, STL priority_queue로 min heap을 구현하는데 원래 좌표까지 저장하려다보니 좀 복잡해진다.. 다른 사람이 짜놓은 깔끔한 코드가 있다면 참조해서 공부해야겠다..

 

#include <queue>
#include <vector>
#include <math.h>
#include <iostream>

using namespace std;

typedef pair<double,pair<int,int>> Route;
typedef struct {
	bool operator()(Route a, Route b) {
		return a.first > b.first;
	}
}RouteComp;


const int MAX_N = 105;
vector<pair<float,float>> star;
priority_queue<Route,vector<Route>,RouteComp> edge;
vector<int> uf_parent;
double cost_sum = 0;
int n;

int uf_find(int a) {
	if(uf_parent[a]==a) return a;
	else return uf_find(uf_parent[a]);
}

void uf_union(int a, int b) {
	int root_a = uf_find(a);
	int root_b = uf_find(b);
	if(root_a == root_b) return;
	uf_parent[root_b] = root_a;
	uf_parent[b] = root_a;
}

bool uf_check() {
	for(int i = 0 ; i< n; i++) {
		if(uf_find(i) != uf_find(0)) 
			return false;
	}
	return true;
}


int main(void) {
	cin.tie(NULL);cout.tie(NULL);ios_base::sync_with_stdio(false);
	
	float temp1,temp2;
	double cost;
	
	cin>>n;
	for(int i = 0; i < n; i ++) {
		cin>>temp1>>temp2;
		star.push_back(make_pair(temp1,temp2));
		uf_parent.push_back(i);
	}
	
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j++) {
			if(i==j) continue;
			cost = sqrt(pow(star[i].first- star[j].first,2) + pow(star[i].second - star[j].second, 2) );
			edge.push(make_pair(cost, make_pair(i,j)));
		}
	}
	
	while(!edge.empty()) {
		Route current = edge.top();
		edge.pop();
		if(uf_find(current.second.first) == uf_find(current.second.second)) continue;
		cost_sum += current.first;
		uf_union(current.second.first, current.second.second);
		if(uf_check()) break;
	}
	cout<< cost_sum;
	
	return 0;
}

 

이 코드는 내 github에서도 확인할 수 있다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/4386/4386.cpp

GitHub - Jordano-Jackson/PS: Problem solving