백준 4386번 _ 별자리 만들기

2020-04-06 · 배운 것 · 5분 읽기

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

4386번: 별자리 만들기

1. 풀이 방법

최장신장트리를 만드는 문제다.
조금 다른 점이 있다면 가중치가 주어지는게 아니라 만들어야한다는것만 주의하면된다.

내 풀이 방법을 말하자면
1) 별들의 좌표를 저장한다.
2) 별들 간의 모든 거리를 구해 우선순위 큐에 넣는다.
3) 크루스칼 알고리즘을 사용한다. ( 우선순위 큐를 가중치 기준으로 세팅하고 이미 연결이 된 점이면 넘어가고 연결이 안됬다면 이어주기 )

2. 코드

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

using namespace std;

class starInfo
{
public:
	int u;
	int v;
	double distance;
	starInfo(int u_in, int v_in, double distance_in)
		:u(u_in), v(v_in), distance(distance_in)
	{}
};

struct cmp
{
	bool operator() (const starInfo& a, const starInfo& b)
	{
		return a.distance > b.distance;
	}
};

vector<pair<double, double>> starPoints;
priority_queue<starInfo, vector<starInfo>, cmp> pri_que;
int parents[102];

double getDistanceEachOther(pair<double, double> a, pair<double, double> b)
{
	double x1 = a.first;
	double y1 = a.second;
	double x2 = b.first;
	double y2 = b.second;
	return sqrt(pow((x2 - x1), 2) + pow((y2 - y1), 2));
}

void parentsInit(int n)
{
	for (int i = 1; i <= n; i++)
		parents[i] = i;
}

int getParents(int a)
{
	if (parents[a] == a) return a;
	return getParents(parents[a]);
}

void Union(int a, int b)
{
	a = getParents(a);
	b = getParents(b);
	parents[b] = a;
}

int main()
{
	int n;
	cin >> n;
	parentsInit(n);

	//걍 계산하기 편하려고  이렇게 함
	starPoints.resize(101);
	double x, y;
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y;
		starPoints[i] = { x, y };
	}

	//별끼리의 거리데이터를 만든다.
	for (int u = 1; u <= n; u++)
	{
		for (int v = u+1; v <= n; v++)
		{
			//같은 점끼리의 거리는 구할필요가없다.
			if (u == v)
				continue;

			double distance = getDistanceEachOther(starPoints[u], starPoints[v]);
			pri_que.push(starInfo(u, v, distance));
		}
	}

	//우선순위 큐를 꺼내며 별들을 이어본다
	double answer = 0;
	while (!pri_que.empty())
	{
		int u = pri_que.top().u;
		int v = pri_que.top().v;
		double distance = pri_que.top().distance;
		pri_que.pop();

		//이미 이어져있는지 확인
		if (getParents(u) == getParents(v))
			continue;

		//안이어져 있다면 이어주기
		Union(u, v);

		answer += distance;
	}

	cout << fixed << setprecision(2) << answer << '\n';
	return 0;
}

3. 후기

문제는 쉽지만 작성할 코드는 꽤 있는 편이다.