[백준 / BOJ] C++ 1774 우주신과의 교감

1774번: 우주신과의 교감

 

문제

https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

 

 

풀이

모든 우주신들 간 최단 통로로 연결이 되어있어야 하므로 최소 스패닝 트리(MST)를 구하면 된다. 모든 우주신의 좌표를 입력받은 후 서로 간의 거리를 모두 구해 간선으로 추가한다. 이후 이미 연결된 통로인 경우에는 미리 두 점을 union 시켜 MST에서 제외시켜 주고 크루스칼 알고리즘을 사용해 MST를 구한다. 이때 구해지는 가중치의 합이 추가로 연결해야 하는 최소의 통로 길이다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> p;

int find(int x) {
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int x, int y) {
  x = find(x);
  y = find(y);
  if (x < y)
    p[y] = x;
  else
    p[x] = y;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M;
  vector<pair<double, pair<int, int>>> edge;
  cin >> N >> M;
  p.resize(N + 1);
  iota(p.begin(), p.end(), 0);
  vector<pair<int, int>> pos(N + 1); // 우주신들의 좌표를 저장할 벡터
  for (int i = 1; i <= N; i++) // 우주신들의 좌표 저장
    cin >> pos[i].first >> pos[i].second;
  // 모든 우주신들에 대해 서로의 거리 간선으로 추가
  for (int i = 1; i <= N; i++)
    for (int j = i + 1; j <= N; j++) {
      auto [x1, y1] = pos[i];
      auto [x2, y2] = pos[j];
      double d = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
      edge.push_back({d, {i, j}});
    }
  // 이미 연결된 통로는 union
  while (M--) {
    int a, b;
    cin >> a >> b;
    merge(a, b);
  }
  // 크루스칼 알고리즘
  double ans = 0;
  sort(edge.begin(), edge.end());
  for (auto [weight, path] : edge)
    if (find(path.first) != find(path.second)) {
      ans += weight;
      merge(path.first, path.second);
    }
  // 소수점 둘째자리까지 출력
  cout.precision(2);
  cout << fixed << ans;
  return 0;
}