[4386_스폐셜 저지] 별자리 만들기 - MST ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

---

[ 문제 접근 ]

MST 문제인건 알겠는데 우선 엣지를 어떻게 입력 받을까 고민했었고,

소수점 출력하는법을 까먹어서 찾아봤다.

 

MST 는 Kruskal과 Prim(우선순위큐 사용) 으로 풀 수 있는데

Kruskal 로 풀어봤다.

 

// <kruskal>
// 1.make-set ( 모든 노드 개별 집합으로 표현 )
// 2.edge들을 오름차순 정렬.
// 3.모든 엣지에 대해서 작은거 부터 find , union
// 4. 선택한 엣지가 n-1개 일때까지.

---

[ 최종 코드 ]

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>

using std::cout; using std::cin;
using std::vector;

struct Edge {
	int node[2];
	double cost;
	Edge(int _a, int _b, double _cost) :cost(_cost) {
		node[0] = _a;
		node[1] = _b;
	}
	bool operator<(const Edge& e)const {
		return cost < e.cost;
	}
};

vector<std::pair<double, double>> nodes;
vector<Edge> edges;
double x, y, distance;
int n;
int parent[101];
int tree_size[101];

int findSet(int a) {
	if (parent[a] == a) return a;
	return findSet(parent[a]);
}

void unionSet(int a, int b) {
	a= findSet(a);
	b= findSet(b);
	if (tree_size[a] > tree_size[b]) {
		parent[b] = a;
		tree_size[b] += tree_size[a];
	}
	else {
		parent[a] = b;
		tree_size[a] += tree_size[b];
	}
}

// kruskal 이용
// 1.make-set ( 모든 노드 개별 집합으로 표현 )
// 2.edge들을 오름차순 정렬.
// 3.모든 엣지에 대해서 작은거 부터 find , union
// 4. 선택한 엣지가 n-1개 일때까지.

void mst() {
	double answer = 0.00f;
	for (int i = 0; i < n + 1; i++) { // 0 번 노드 부터 사용
		parent[i] = i;
	}
	std::fill_n(tree_size, n + 1, 1);
	std::sort(edges.begin(), edges.end());
	int cnt = 0;

	// 모든 엣지에 대해서
	for (int i = 0; i < edges.size() && cnt < n-1 ; i++) {
		int node1 = edges[i].node[0];
		int node2 = edges[i].node[1];
		double temp_cost = edges[i].cost;

		// 두 노드의 부모가 다르면
		if (findSet(edges[i].node[0]) != findSet(edges[i].node[1])) {
			unionSet(edges[i].node[0], edges[i].node[1]);
			answer += temp_cost;
			cnt++;
		}
	}
	cout << std::fixed;
	cout.precision(2);
	cout << answer;
}


int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n;
	nodes.reserve(n + 1);
	double _cost;
	int t = n;
	while (t--) { // 이거 진짜 조심해야겠다. 또 실수 했네 여기서 n-- 하니깐 밑에 for 문 들어가지도 못하고 바로 나오네 차라리 입력 for문으로 받아야겠다.
		cin >> x >> y;
		nodes.push_back({ x,y });
	}

	for (int i = 0; i < n-1; i++) {
		for (int j = i+1; j < n; j++) {
			double x_diff = nodes[j].first - nodes[i].first;
			double y_diff = nodes[j].second - nodes[i].second;
			distance = sqrt(std::pow(x_diff, 2) + std::pow(y_diff, 2));
			edges.push_back(Edge(i, j, distance));
		}
	}
	mst();
	
	return 0;
}

---

[ 조심할 점 ]

입력 받을때 while 문이 편해서 이렇게 받는데 문제는 while문 돌면서 n-- 되는걸 망각하고

 

다음 어디든 n ( 노드의 개수 ) 를 사용하려고 하는것이다. ( 까먹지 말자 ! )

while (n--) { 
		cin >> x >> y;
		nodes.push_back({ x,y });
	}

---

[ Key Point ]

 

👉 문제에서 두 점의 좌표만 줬을때, 우리가 필요한건 점과 점 사이의 거리인 cost 니깐 edges로 넘겨줘야한다.

for (int i = 0; i < n-1; i++) {
		for (int j = i+1; j < n; j++) {
			double x_diff = nodes[j].first - nodes[i].first;
			double y_diff = nodes[j].second - nodes[i].second;
			distance = sqrt(std::pow(x_diff, 2) + std::pow(y_diff, 2));
			edges.push_back(Edge(i, j, distance));
		}
	}

 

👉 소수점 출력

cout << std::fixed;
cout.precision(2);
cout << answer;

cout << std::fixed   해주지 않으면 실수 포함해서 N자리 나온다.

fixed를 해줘야 원하는 소수 자리수 표현 가능 ( 고정 소수점으로 쓴다는 말 같다.)

 

---

[ 다른 사람 풀이 ]

 

ref : https://yabmoons.tistory.com/404

ref : https://takeknowledge.tistory.com/13

ref : https://dev-mb.tistory.com/267