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

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

#include #define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define INF 987654321 using namespace std; //루트 노드를 찾아주는 코드 typedef pair pii; vector star; int parent[5052]; int N; struct st { int s, e; float c; }; st arr[5052]; bool compare(st a, st b) { return a.c < b.c; } int find(int a) { //a가 root임 //cout << "find a =" << a << "

"; if (parent[a] < 0) return a; //a가 root가 아닐때 return parent[a] = find(parent[a]); } int merge(int a, int b) { a = find(a); b = find(b); //cout << "merge" << a << "" << b << "

"; if (a == b)return 0; //small to large if (parent[a] > parent[b]) swap(a, b); parent[a] += parent[b]; parent[b] = a; return 1; } void slove() { //간선이 작은 순으로 정렬 sort(arr, arr + (N)*(N-1)/2, compare); float ans=0; for (int i = 0; i <= (N)*(N - 1)/2; i++) parent[i] = -1; for (int i = 0; i < (N)*(N - 1)/2; i++) { if (merge(arr[i].s, arr[i].e)) { //cout << "arr[i].s =" << arr[i].s << " arr[i] = " << arr[i].e << "

"; ans += arr[i].c; } } cout << ans << "

"; } float havorsine(float a, float b, float c, float d) { return sqrt((a-c)*(a-c)+ (b-d)*(b-d)); } int main() { FASTIO; float a, b, c; int cnt =0; cin >> N; for (int i = 0; i < N; i++) { cin >> a >> b ; star.push_back({ a,b }); } for (int i = 0; i

크루스칼 알고리즘을 이용하여 MST 를만들어서 풀었다.

vector 와 struct 사용이 좀 미숙해서 꽤나 오래 걸렸다.

그리고 N개의 입력을 받아서 배열을 N의 최대 개수로 설정했는데

N*(N-1)/2 개를 해야해서 한번 틀렸다.

from http://kerryfrog.tistory.com/40 by ccl(A) rewrite - 2021-09-30 00:26:44