[문제]
https://www.acmicpc.net/problem/1774
[풀이]
별자리 만들기 문제와 같은 최소 신장 트리 유형이다.
마찬가지로 크루스칼 알고리즘을 이용해서 풀이하였고, 이미 연결된 통로들에 대해 미리 입력받아 처리한다.
[코드]
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <tuple>
#define INF 987654321
using namespace std;
int n, m;
int parent[1001];
vector<tuple<double, int ,int>> dist;
struct position {
int x, y;
};
int find(int u){
if(parent[u]==u) return u;
else return parent[u] = find(parent[u]);
}
bool union_node(int u, int v){
u = find(u);
v = find(v);
if(u==v) return false; //연결하면 사이클 생김
else {
parent[u] = v;
return true;
}
}
double cal_dist(int x1, int y1, int x2, int y2){
return sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//mst
cin >> n >> m;
vector<position> god;
god.push_back({0, 0});
for(int i=0; i<n; i++){
int x, y;
cin >> x >> y;
god.push_back({x, y}); //우주신 위치
}
for(int i=1; i<=n; i++){
parent[i] = i;
}
for(int i=0; i<m; i++){
int u, v;
cin >> u >> v;
union_node(u, v); //이미 연결된 통로들
}
for(int i=1; i<=n-1; i++) {
for (int j = i + 1; j <= n; j++) {
double r = cal_dist(god[i].x, god[i].y, god[j].x, god[j].y);
dist.push_back({r, i, j});
}
}
sort(dist.begin(), dist.end());
double ans = 0.0;
for(int i=0; i<dist.size(); i++){
int u = get<1>(dist[i]);
int v = get<2>(dist[i]);
double cost = get<0>(dist[i]);
if (union_node(u, v))
ans += cost;
}
printf("%.2lf", ans);
}
'알고리즘 공부 및 문제 풀이 > 백준(BOJ)' 카테고리의 다른 글
[boj] 백준 1941 소문난 칠공주 (c++) - DFS, BFS (0) | 2022.12.12 |
---|---|
[boj] 백준 13904 과제 (c++) - 그리디 (0) | 2022.12.09 |
[boj] 백준 14442 벽 부수고 이동하기 2 (c++) - BFS (0) | 2022.12.02 |
[boj] 백준 20057 마법사 상어와 토네이도 (c++) - 시뮬레이션 (0) | 2022.11.30 |
[boj] 백준 1613 역사 (c++) - 플로이드-와샬 (0) | 2022.11.28 |