문제 URL : https://www.acmicpc.net/problem/4386
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일�
www.acmicpc.net
문제 접근법 : 좌표평면의 모든점들을 이어줘야하기때문에 네트워크로 따지면 망형(Mesh)구조가 성립되기때문에
공식대로 모든 선들은 n(n-1)/2 개의 연결선이 생깁니다. 물론 연결선은 좌표평면의 두점사이의 거리로 쉽게 구할수있고 망형구조의 모든 연결선을 만들고 난후 최소스패닝 트리구조를 만들어야 하기때문에
kruskal알고리즘을 이용해서 풀면 됩니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
//By 콩순이냉장고
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <functional>
#include <cmath>
using namespace std;
int n;
typedef pair<double, double> p;
vector<p> v;
vector<pair<double, pair<int, int>>>v2;
int parent[100];
double Distance(p a, p b)
{
return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}
int find(int idx)
{
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}
void Union(int idx1, int idx2)
{
parent[idx2] = idx1;
}
void kruskal(){
sort(v2.begin(), v2.end());
double sum = 0;
for (int i = 0; i < v2.size(); i++)
{
int left = find(v2[i].second.first);
int right = find(v2[i].second.second);
if (left != right)
{
sum += v2[i].first;
Union(left, right);
}
}
cout << sum << "\n";
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++)
parent[i] = i;
for (int i = 0; i < n; i++)
cin >> v[i].first >> v[i].second;
for (int i = 0; i < n -1; i++)
{
for (int j = i+1; j < n; j++){
v2.push_back({ Distance(v[i], v[j]), { i, j } });
}
}
kruskal();
}
|
cs |
궁금한점 혹은 모르는점 혹은 제 생각에 틀린점이 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'백준' 카테고리의 다른 글
| 백준 5373 큐빙(SW 역량 테스트 기출 문제) (0) | 2020.09.21 |
|---|---|
| 백준 4195 친구 네트워크 (0) | 2020.08.30 |
| 백준 1922 네트워크 연결 (0) | 2020.08.30 |
| 백준 5557 1학년 (0) | 2020.08.26 |
| 백준 10473 인간 대포 (0) | 2020.08.25 |
