[C++] 백준 4386번: 별자리 만들기

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

4386번: 별자리 만들기

 

풀이

유니온-파인 알고리즘의 개념과 이미 연결되어 있는 그래프를 파악하여 그래프에 사이클이 존재하는지 여부를 지속적으로 확인하여 줍니다. 이러한 기법을 크루스칼 알고리즘 또는 최소 스패닝 트리라고 합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

class edge {
public:
	int node[2];
	float distance;

	edge(int a, int b, float c) {
		this->node[0] = a;
		this->node[1] = b;
		this->distance = c;
	}

	bool operator <(edge& edge) {
		return this->distance < edge.distance;
	}
};

int parent[101];

int find(int index) {
	if (parent[index] == index) return index;
	return parent[index] = find(parent[index]);
}

void uni(int a, int b) {
	a = find(a);
	b = find(b);
	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
}

//사이클 유무 확인
bool isCycle(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return true;
	else
		return false;
}

float Distance(pair<float, float> a, pair<float, float>b) {
	return sqrt(pow((a.first - b.first),2) + pow((a.second - b.second),2));
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<edge>v;
	vector<pair<float, float>>star;

	int V;
	float a, b;
	cin >> V;

	for (int i = 0; i < V; i++)
		parent[i] = i;

	for (int i = 0; i < V; i++) {
		cin >> a >> b;
		star.push_back(make_pair(a, b));
	}

	for (int i = 0; i < V; i++) {
		for (int j = i; j < V; j++) {
			v.push_back(edge(i, j, Distance(star[i], star[j])));
		}
	}

	//거리순 정렬
	sort(v.begin(), v.end());

	float answer = 0;

	for (int i = 0; i < v.size(); i++) {
		if (isCycle(v[i].node[0], v[i].node[1]) == false) {
			answer += v[i].distance;
			uni(v[i].node[0], v[i].node[1]);
		}
	}

	//fixed를 통해 소수의 유효자리 수를 고정시킴
	cout << fixed;
	cout.precision(2);
	cout << answer;

	return 0;
}