👓 문제 설명
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.
- 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
- 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.
별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.
💣 제한 사항
- 첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)
- 둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.
- 첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.
🚨 접근 방법
최소 비용 신장 트리 (MST)의 문제이다.
N개의 정점이 있을 때, 최소한의 비용으로 모든 정점을 연결하는 알고리즘을 뜻한다.
간선의 개수는 N-1개이며, 사이클이 존재하면 안된다.
크게 2가지가 있다.
1. 크루스칼 알고리즘
이 기법은 Union-Find 기법을 활용해
현재 연결된 간선들이 사이클이 있는지 판단하고, 가장 가중치가 낮은 간선을 선택하여 그룹을 형성한다.
2. 프림 알고리즘
이 기법은 임의의 정점을 하나 선택하고 해당 정점과 이어진 모든 정점을 우선순위 큐에 저장한다.
이 때 간선의 비용이 낮은 것이 우선순위를 갖는다. 이후, 방문하지 않은 정점에 한하여 우선순위 큐에서 꺼낸 후 방문처리를 진행한다.
본 문제는 2번 프림 알고리즘을 통해 해결했다.
프림 알고리즘은 정점의 개수가 낮을 때 활용하면 좋다.
🚈 풀이
#include<iostream>
#include<climits>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#define MAX DBL_MAX
using namespace std;
double pos[101][2];
vector<pair<double, int>>info[101];
bool visited[101];
int n;
double ans;
void calDist() {
for (int i = 1; i <= n; i++) {
double a, b;
cin >> a >> b;
pos[i][0] = a;
pos[i][1] = b;
}
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
double d = sqrt(pow(pos[i][0] - pos[j][0], 2) + pow(pos[i][1] - pos[j][1], 2));
info[i].push_back({ d,j });
info[j].push_back({ d,i });
}
}
}
void Prim() {
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>>pq;
for (int i = 0; i < info[1].size(); i++) {
pq.push(info[1][i]);
}
visited[1] = true;
// 임의의 정점 하나 선택 후 연결된 모든 간선 저장
// 가장 비용이 작은 간선의 정점부터 연결
while (!pq.empty()) {
double dis = pq.top().first;
int now = pq.top().second;
pq.pop();
if (visited[now])continue;
visited[now] = true;
ans += dis;
for (int i = 0; i < info[now].size(); i++) {
double next_dis = info[now][i].first;
int next = info[now][i].second;
if (!visited[next])pq.push(info[now][i]);
}
}
}
int main() {
cin >> n;
calDist();
Prim();
cout << ans;
return 0;
}