백준 4386번 별자리 만들기 C++ MST, 최소 신장 트리

리뷰

각 노드의 좌표를 입력 받고 모든 노드를 연결하는 가장 적은 거리를 도출하는 MST 문제

 

문제 풀이

1. n줄에 걸쳐 입력되는 모든 좌표 값을 lst 벡터에 추가 해준다.
2. float, int, int 형식의 튜플 벡터 edges를 초기화 해준다.
3. 각 노드간의 거리를 모두 구해 edges 벡터에 거리, 시작 노드, 도착 노드 순으로 추가해 준다.
4. 이후 edges 벡터를 거리 순으로 오름차순 정렬 해주고 유니온 파인드를 통해 최소 신장 트리를 구한다.
5. 최소 신장 트리를 과정에서 float 변수 sum에 누적 거리를 저장해 주고 소숫점 2자리 까지 출력해 준다.

 

참고 사항

좌표가 float 형식으로 입력 되지만 vector<pair<int, int>> 형식으로 입력 받아도 통과 하는걸 보니 정수형으로 입력 받아도 무방한 것 같다.

 

 

정답 코드

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

using namespace std;

int nodes[101];
int n;

vector<pair<float, float>> lst;

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int rootA = Find(a);
	int rootB = Find(b);
	if (rootA == rootB) return;
	nodes[rootB] = rootA;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		float x, y;
		cin >> x >> y;
		lst.push_back({ x, y });
	}

	vector<tuple<float, int, int>> edges;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			float x1 = lst[i].first, y1 = lst[i].second;
			float x2 = lst[j].first, y2 = lst[j].second;
			float dist = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
			edges.push_back({ dist, i, j });
		}
	}
	sort(edges.begin(), edges.end());

	for (int i = 1; i <= n; i++) {
		nodes[i] = i;
	}

	float sum = 0;
	for (int i = 0; i < edges.size(); i++) {
		tuple<float, int, int> cur = edges[i];
		if (Find(get<1>(cur)) == Find(get<2>(cur))) continue;
		Union(get<1>(cur), get<2>(cur));
		sum += get<0>(cur);
	}
	printf("%.2f", sum);
}