[C++]백준 - 4386번 문제

4386번: 별자리 만들기 (acmicpc.net)

4386번: 별자리 만들기

 

4386번 : 별자리 만들기

---

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

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

 

입력

---

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

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

각 별들 간의 거리를 구하여 에지를 만들기만 하면, 크루스칼 알고리즘을 이용해 풀 수 있습니다.

 

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct edge
{
    int a;
    int b;
    double cost;
};

bool sorting(edge a, edge b)
{
    return a.cost < b.cost;
}

//거리 구하기
double get_distance(pair<double, double> a, pair<double, double> b)
{
    double l1 = a.first - b.first;
    double l2 = a.second - b.second;
    return sqrt(l1 * l1 + l2 * l2);
}

//부모찾기
int get_parent(int parents[], int target)
{
    while(target != parents[target]) target = parents[target];
    return target;
}

//유니온 파인드
bool set_union(int parents[], int a, int b)
{
    a = get_parent(parents, a);
    b = get_parent(parents, b);
    
    if(a == b) return false;
    parents[b] = a;
    return true;
}

int main() 
{
    int N;
	scanf("%d", &N);
	
	int *parents = new int[N];
	pair<double, double> *stars = new pair<double, double>[N];
	for(int i = 0; i < N; i++) 
	{
	    scanf("%lf %lf", &stars[i].first, &stars[i].second);
	    parents[i] = i;
	}

    //에지 만들기
	vector<edge> v;
	for(int i = 0; i < N; i++)
	{
	    for(int j = i + 1; j < N; j++)
	    {
	        edge e;
	        e.a = i;
	        e.b = j;
	        e.cost = get_distance(stars[i], stars[j]);
	        v.push_back(e);
	    }
	}
	sort(v.begin(), v.end(), sorting);
	
	double result = 0;
	//크루스칼
	for(edge e : v)
	{
	    if(set_union(parents, e.a, e.b)) result += e.cost; 
	}
    printf("%.2lf", result);
	
	delete[] stars;
	delete[] parents;
	return 0;
}

 

그 외

---