baekjoon 4386:별자리 만들기

baekjoon 4386 별자리 만들기

4386번 별자리 만들기

접근

처음엔 눈치채지 못했지만 이 문제는 전형적인 mst문제이다.
각 별을 모두 연결하는 연결 그래프를 만들고 거기서 mst를 만들면 된다.
mst를 만드는 알고리즘으로는 kruskal알고리즘을 사용했다.
kruskal알고리즘은 모든 edge를 weight 오름차순으로 정렬해두고 작은것 부터 방문하며
만약 그 edge가 서로 다른 component에 있는 두 점을 연결한다면 추가하는 방식으로 mst를 구한다.
서로 다른 component에 있는지는 union-find알고리즘을 이용한다. find(x)는 x가 속한 component의 root node를 return한다.
merge(x, y)는 만약 둘이 find결과 같으면 같은 component에 있단 소리니까 병합하지 않고, 다르다면 한쪽의 root node가 다른쪽의
root node를 가리키도록 하여 같은 component로 합쳐버린다.
0.01까지 오차를 허용하니까 setpercision함수를 통해 0.01까지만 표현한다. fixed를 표현하면 소수부 자릿수만 count된다.

코드

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
array<int, 100> uf;
int find(int x){
  if(uf[x] == x) return x;
  return uf[x] = find(uf[x]);
}
bool merge(int x, int y){
  int rootx = find(x);
  int rooty = find(y);
  if(rootx == rooty) return false;
  uf[rooty] = rootx;
  return true;
}
struct Edge{
  int u, v;
  float w;
  Edge(int u1, int v1, float w1): u(u1), v(v1), w(w1){}
  bool operator<(const Edge& other)const{ return w < other.w; }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<pair<float, float>> vertex;
  for(int i = 0; i < n; i++){
    float x, y; cin >> x >> y;
    vertex.push_back({x, y});
  }
  vector<Edge> edges;
  for(int i = 0; i < n; i++){
    for(int j = i+1; j < n; j++){
      float dx = abs(vertex[i].first - vertex[j].first);
      float dy = abs(vertex[i].second - vertex[j].second);
      float length = sqrt(dx*dx + dy*dy);
      edges.push_back({i, j, length});
    }
  }
  sort(edges.begin(), edges.end());
  for(int i = 0; i < n; i++){
    uf[i] = i;
  }
  int cnt = 0; float result = 0;
  for(int i=0; ; i++){
    if(merge(edges[i].u, edges[i].v)){
        result += edges[i].w;
        if(++cnt == n-1) break; // N-1개 간선을 뽑으면 나감
    }
  }
  cout << fixed << setprecision(2) << result; 
  
  
}

배운 점

kruskal 알고리즘, union-find, setprecision 3가지 로직이 사용되었다.