BOJ 4386 별자리 만들기

www.acmicpc.net/problem/4386

4386번: 별자리 만들기

보자마자 greedy하게 짧은 간선들을 선택하면 어떨까 생각을 하였고, 이게 정답을 항상 낸다는 보장이 있나 생각하던 찰나에 이와 완전히 같은 크루스칼 알고리즘이 생각났다.

크루스칼 알고리즘 증명은 위키에도 있지만, 추후에 정리해보도록 하자.

ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#%EC%A0%95%ED%99%95%EC%84%B1_%EC%A6%9D%EB%AA%85

크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전

코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

struct{
  int parent;
  double x;
  double y;
  double total_cost;
  int total_node;
}typedef Node;

vector<pair<double, pair<int, int>>> vertex;
Node nodes[100];
int n;

int find(int a){
  if(nodes[a].parent==a)
    return a;
  else
    return nodes[a].parent = find(nodes[a].parent);
}

bool merge(int a, int b){
  int a_p = find(a);
  int b_p = find(b);
  Node& a_n = nodes[a_p];
  Node& b_n = nodes[b_p];
  
  if(a_p != b_p){
    a_n.total_cost += b_n.total_cost;
    a_n.total_cost += sqrt(pow(nodes[a].x-nodes[b].x, 2) + pow(nodes[a].y-nodes[b].y, 2));
    a_n.total_node += b_n.total_node;
    b_n.parent = a_p;
    printf("total_node : %d\n",a_n.total_node);
    return true;
  }
  else
    return false;
}

int main(){

  double answer = 0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%lf%lf",&(nodes[i].x), &(nodes[i].y));
    nodes[i].parent = i;
    nodes[i].total_node = 1;
  }


  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      double cost = sqrt(pow(nodes[i].x-nodes[j].x, 2) + pow(nodes[i].y-nodes[j].y, 2));
      vertex.push_back({cost,{i,j}});
    }
  }

  sort(vertex.begin(), vertex.end());

  for(auto it : vertex){
    int f = it.second.first;
    int s = it.second.second;
    double c =it.first;

    bool result = merge(f, s);
    //printf("%d %d %.2f : %d\n", f, s, c , result);
    //printf("%d\n",nodes[find(f)].total_node);
    
    if(nodes[find(f)].total_node == n){
      answer = nodes[find(f)].total_cost;
      break;
    }
  }

  printf("%.2f\n", answer);

  return 0;
}

 

merge 함수 밖에서 cost를 합치는 작업을 하기 싫어서 위의 code처럼 merge 함수를 구현했는데, cost를 paremeter로 넘겨줬다면 좀 더 깔끔한 코드가 됬을 것 같다는 생각이 들었다.