(BOJ) 4386 별자리 만들기

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

 

문제 풀이:

mst를 사용한 문제

각 점들의 (x,y)값을 입력 받아 벡터에 저장하고

한 별에서 다른 별들로 갈 수 있는 모든 경로의 길이를 priority_queue에 저장

가장 짧은 길이를 가진 두 별을 팝해와서 이미 연결된 노드는 패스하고 아니면 연결해주고 그 길이를 res에 더해줌

최소만 연결하면 n-1개의 다리(?)가 생기므로 다 연결했으면 바로 break해주면 됨 

 

소스 코드:

typedef pair<double,pair<int, int>> P;
int n,p[101],cnt;
double res;
bool visit[101];
vector<pair<double,double>> adj;
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;
	memset(p, -1, sizeof(p));
	for (int i = 0; i < n; i++) {
		double q, w;
		cin >> q >> w;
		adj.push_back({ q,w });
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			pq.push({ sqrt(pow(adj[i].first - adj[j].first,2)+pow(adj[i].second - adj[j].second,2)),{i,j} });
		}
	}
	while (!pq.empty()) {
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		double c = pq.top().first;
		pq.pop();

		if (merge(x, y)) {
			res += c;
			cnt++;
			if (cnt == n - 1) break;
		}
	}
	cout << fixed << setprecision(2) << res << '\n';
}