글 읽기 - [틀렸습니다] MST 질문(크루스칼)

wony6731 4년 전 0

MST를 처음 공부하고 배운대로 코드를 적용하여 구현해보았습니다.

"1197번 - 최소 스패닝 트리"와 MST 구현은 동일한 것 같은데

어느 부분에서 제가 놓치고 있는지 알 수 있을까요...?

MST를 처음하다보니 어디서부터 잘못되었는지 찾기가 조금 힘든것같아요...ㅎㅎ

/*
	Title : 별자리 만들기
	Description
		- n 개의 별
		- 모든 별들은 직/간접 연결
		- 별자리르 만드는 최소 비용은?
	Solution
	*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>

using namespace std;

int v;
int cnt = 0;
double sum = 0;
vector<pair<double, pair<int, int>>> edge;
vector<int> p(5000, -1);

double GetDist(double x1, double y1, double x2, double y2);
int find(int x);
bool is_diff_group(int u, int v);

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> v;
	vector<pair<double, double>> V;
	for (int i = 0; i < v; i++){
		double x, y;
		cin >> x >> y;
		V.push_back(make_pair(x, y));
	}

	// 별 하나
	if (v == 1){
		cout << "0\n";
		return 0;
	}

	// 별 사이의 거리 계산
	int idx1 = 0;
	int idx2 = 1;
	double dist = 0;
	while (true){
		while (true){
			dist = GetDist(V[idx1].first, V[idx1].second, V[idx2].first, V[idx2].second);
			edge.push_back(make_pair(dist, make_pair(idx1 + 1, idx2 + 1)));
			idx2++;
			if (idx2 == v){
				idx2 = idx1 + 2;
				break;
			}
		}
		idx1++;
		if (idx1 == v - 1 && idx2 == v)
			break;
	}

	// 간선 가중치 정렬
	sort(edge.begin(), edge.end());

	// MST
	for (int n = 0; n < v; n++){
		double cost = edge[n].first;
		int v1 = edge[n].second.first;
		int v2 = edge[n].second.second;

		// 같은 그룹이면 pass
		if (!is_diff_group(v1, v2)) continue;

		sum += cost;
		cnt++;

		if (cnt == v - 1)
			break;
	}

	//printf("%.2f\n", sum);
	//cout << sum << "\n";
	cout << fixed << setprecision(2) << sum << '\n';

	return 0;
}

double GetDist(double x1, double y1, double x2, double y2){
	return pow(pow(abs(x2 - x1), 2) + pow(abs(y2 - y1), 2), 1.0 / 2.0);
}

bool is_diff_group(int u, int v){
	u = find(u);
	v = find(v);

	if (u == v)
		return false;
	else if (u <= v)
		p[v] = u;
	else
		p[u] = v;

	return true;
}

int find(int x){
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[틀렸습니다] MST 질문(크루스칼)

wony6731 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말