백준 알고리즘 4386번 : 별자리 만들기

링크

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

문제

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

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
  별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

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

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

출력

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

예제 입력 및 출력

풀이법

그동안 풀었던 MST문제들과는 다르게 간선을 직접 계산해서 추가해주어야합니다. 실수형으로 입력되므로 Edge 구조체를 선언시에 가중치(w부분)을 실수형을 사용하였습니다.
소수점 2번째 자리까지 출력하기 위해서 c++ 문법인 fixed를 사용해도 되지만 c문법인 .2f를 사용하였습니다.

풀이 코드(C++)

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define MAX 1005
#define INF 1e9+7
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double; 
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdbl = pair<double, double>;
using vi = vector<int>;
#define sz(a) int((a).size())

struct UnionFind {
	vector<int> parent, rank, cnt, check;
	UnionFind(int n) : parent(n), rank(n, 1), cnt(n, 1), check(n) {
		iota(parent.begin(), parent.end(), 0);
	}
	int Find(int x) {
		return x == parent[x] ? x : parent[x] = Find(parent[x]);
	}
	bool Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return 0;
		if (rank[a] < rank[b]) swap(a, b);
		parent[b] = a;
		rank[a] += rank[a] == rank[b];
		cnt[a] += cnt[b];
        check[a] |= check[b];
		return 1;
	}
};

struct Edge{
  int u,v;
  double w;
  Edge(int u1,int v1, double w1): u(u1),v(v1),w(w1){}
  bool operator < (const Edge& O)const{ return w < O.w; }; // 오름차순 정렬
};

int main(){
  fastio;
  int n; cin >> n;
  vector<pdbl> point(n);
  vector<Edge> e;
  for(int i = 0; i < n; i++){
    double a,b; cin >> a >> b;
    point[i].x = a; point[i].y = b;
  }
  // 거리 계산
  for(int i = 0; i < point.size(); i++){
    for(int j = i + 1; j < point.size(); j++){
      double c = sqrt(((point[i].x - point[j].x) * (point[i].x - point[j].x)) + ((point[i].y - point[j].y)*(point[i].y - point[j].y)));
      e.pb(Edge(i ,j ,c));
    }
  }
  sort(e.begin(), e.end()); // 가중치 기준으로 정렬
  UnionFind UF(n);
  double result = 0;
  int cnt = 0;
  for(int i = 0; ; i++){
    if(UF.Union(e[i].u, e[i].v)){
      result += e[i].w;
      if(++cnt == n - 1) break; // n - 1개 간선을 뽑으면 탈출
    }
  }
  printf("%.2f\n",result);
  return 0;
}