[백준 4386] 별자리 만들기 (C++)

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

4386번: 별자리 만들기

문제

---

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

 

입력

---

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

 

출력

---

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10^-2까지 허용한다.

 

문제 풀이

---

MST 문제.

별자리의 모든 별들이 선을 통해 직간접적으로 연결되어 있으면서도 최소 비용이 들어가게 별자리를 만들려면 별자리의 선들은 MST를 구성해야 한다.

각 별마다 다른 별들까지의 거리를 구해 벡터에 넣어주고, 거리 오름차순으로 정렬한다. 그리고 연결 시 사이클을 형성하는 지 확인 후 사이클을 형성한다면 별자리의 선이 될 수 없고, 사이클이 형성된다면 별자리의 선이 될 수 있으므로 해당 거리만큼의 비용을 더해준다. (kruskal의 방법)

 

아래는 코드.

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
using namespace std;
int* parents;
float answer = 0;
int N;

struct info
{
	int start;
	int end;
	float dist;
	info(int s, int e, float distance)
	{
		start = s;
		end = e;
		dist = distance;
	}
};

vector<pair<float, float>> v;
vector<info> edges;

bool cmp(info& i1, info& i2)
{
	if (i1.dist < i2.dist)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int findParent(int x)
{
	if (parents[x] == x)
	{
		return x;
	}
	else
	{
		return parents[x] = findParent(parents[x]);
	}
}

void merge(int x, int y)
{
	int parentX = findParent(x);
	int parentY = findParent(y);
	if (parentX < parentY)
	{
		parents[parentY] = parentX;
	}
	else
	{
		parents[parentX] = parentY;
	}
}

void calcAllDistance()
{
	for (int i = 1; i < N; i++)
	{
		pair<float, float> currentStar = v.at(i);
		for (int j = 0; j < N; j++)
		{
			pair<float, float> adjacentStar = v.at(j);
			if (i <= j)
			{
				break;
			}
			if (i != j)
			{
				float x = adjacentStar.first - currentStar.first;
				float y = adjacentStar.second - currentStar.second;
				float distance = sqrt(x * x + y * y);
				edges.push_back(info(i, j, distance));
			}
		}
	}
}

void kruskal()
{
	sort(edges.begin(), edges.end(), cmp);
	for (int i = 0; i < edges.size(); i++)
	{
		info current = edges.at(i);
		if (findParent(current.start) == findParent(current.end))
		{
			continue;
		}
		else
		{
			merge(current.start, current.end);
			answer += current.dist;
		}
	}
}

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

	float x, y;
	cin >> N;
	parents = new int[N];
	for (int i = 0; i < N; i++)
	{
		parents[i] = i;
		cin >> x >> y;
		v.push_back(make_pair(x, y));
	}
	calcAllDistance();
	kruskal();
	cout.precision(2);
	cout << fixed;
	cout << answer << "\n";
	return 0;
}