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

4386번: 별자리 만들기

 

문제

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

4386번: 별자리 만들기

 

 

풀이

각 별의 2차원 좌표가 주어지고 별들을 모두 직/간접적으로 최소한의 거리로 이었을 때 거리를 구하는 문제다. 흔한 MST 문제와 달리 약간 생각을 해야한다. 정점 간 가중치가 주어지는 것이 아니기 때문에 각 정점 간 가중치를 직접 구해줘야 한다. 마침 정점의 수 N도 최대 100이므로 모든 정점 간 거리를 구해 간선으로 삼아 MST의 가중치를 구하면 된다. 자료형에 주의하자.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define pdd pair<double, double>

int N;
vector<pdd> graph[100];

double prim() {
  priority_queue<pdd> pq;
  vector<int> visited(N, 0);
  visited[0] = 1;
  for (pdd edge : graph[0])
    pq.push(edge);
  double cost = 0;
  while (!pq.empty()) {
    double weight = -pq.top().first;
    int node = pq.top().second;
    pq.pop();
    if (!visited[node]) {
      visited[node] = 1;
      cost += weight;
      for (pdd next : graph[node])
        if (!visited[next.second])
          pq.push(next);
    }
  }
  return cost;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N;
  vector<pdd> xy(N); // 좌표 값 저장
  for (int i = 0; i < N; i++)
    cin >> xy[i].first >> xy[i].second;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      // 2차원 좌표에서 두 점 사이의 거리 공식
      double dist = sqrt(pow(xy[i].first - xy[j].first, 2) + pow(xy[i].second - xy[j].second, 2));
      // i번 정점과 j번 정점 사이의 잇는 거리를 간선으로 추가
      graph[i].push_back({-dist, j});
      graph[j].push_back({-dist, i});
    }
  cout.precision(2);
  cout << fixed << prim();
  return 0;
}