[백준/C++] 4386번. 별자리 만들기

[백준/C++] 4386번. 별자리 만들기

1. 문제

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

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

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

2. 입력

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

3. 출력

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

4. 풀이

• 최소 신장 트리 문제
• 각 별의 좌표를 입력 받는다.
• 좌표 값을 이용해 각 별 사이의 거리를 구하고 배열에 삽입한다.
• 거리 순으로 별 간의 거리를 정렬한다.
• 현재 선택된 별 사이를 연결했을 때 사이클이 생기지 않으면 거리의 합에 더해주고 둘을 union한다.
• 최종 결과 값 출력

5. 처음 코드와 달라진 점

• 거리 구할 때 d = sqrt(x^2 + y^2)를 해야하는데 d = sqrt(abs(x) + abs(y))를 했다.
• 거리 변수를 int로 선언한 걸 double로 바꾸어주었다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
int parent[101];
vector<pair<double, double> > point;
vector<pair<double, pair<int, int> > > graph;

double getDistance(int x1, int y1, int x2, int y2) {
  return sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));
}

int findParent(int x) {
  if(x == parent[x]) return x;
  else return findParent(parent[x]);
}

void unionParent(int a, int b) {
  a = findParent(a);
  b = findParent(b);

  if(a < b) parent[b] = a;
  else  parent[a] = b;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin>>n;

  for (int i = 0; i < n; i++){
    double x, y;
    cin>>x>>y;
    point.push_back(make_pair(x, y));
  }

  for (int i = 0; i < n; i++){
    parent[i] = i;
  }
  
  
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      graph.push_back(make_pair(getDistance(point[i].first, point[i].second, point[j].first, point[j].second), make_pair(i, j)));
    }
  }

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

  double answer = 0;
  for (int i = 0; i < graph.size(); i++) {
    int a, b;
    double distance;
    distance = graph[i].first;
    a = graph[i].second.first;
    b = graph[i].second.second;

    if(findParent(a) != findParent(b)) {
      answer += distance;
      unionParent(a, b);
    }
  }
  
  cout<<answer;
}