반응형
리뷰
double 조심! int 오버플로우 조심!
각 노드의 좌표가 주어지고 모든 노드를 연결하는 최소값을 구하는 문제
https://www.acmicpc.net/problem/1774
문제 풀이
- n과 m 값을 받아오고 각 노드의 좌표를 구조체 배열로 받아오고, 자신의 인덱스를 value로 갖는 nodes 배열을 초기화
- m줄에 걸쳐 이미 연결되어 있는 노드들 끼리는 Union 처리를 해준다.
- 모든 노드들 간의 간선을 edges 벡터에 저장해 준다. 이때 각 간선의 거리를 구해주어야 한다.
- 간선의 거리를 기준으로 오름차순 정렬해 준 후 모든 노드가 연결 되도록 부분 집합을 활용해 연결해 준다.
- 각 간선이 연결 될때마다 total 변수에 거리의 합을 구해준 후 total을 출력해 준다.
참고 사항
dist를 구할때 좌표를 int로 받았더니 int 오버플로우가 났다, long long으로 명시해 주던가 pow를 사용해서 거리를 구하자
정답 코드
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<cmath>
using namespace std;
int n, m, n1, n2;
int nodes[1001]; // 노드 배열
struct Pos {
int x, y;
};
Pos pos[1001]; // 노드의 좌표 배열
int Find(int a) {
if (nodes[a] == a) return a;
return nodes[a] = Find(nodes[a]);
}
void Union(int a, int b) {
int rootA = Find(a);
int rootB = Find(b);
if (rootA == rootB) return;
nodes[rootB] = rootA;
}
double calcdist(int x1, int y1, int x2, int y2) { // 두 좌표의 거리 구하기
return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int x, y; cin >> x >> y;
pos[i] = { x, y }; // 노드 좌표 저장
nodes[i] = i; // 노드 초기화
}
double total = 0; // 거리 토탈
for (int i = 0; i < m; i++) { // 이미 연결된 케이스
cin >> n1 >> n2;
Union(n1, n2); // 집합을 합쳐준다.
}
vector<tuple<double, int, int>> edges; // 간선 및 간선 간 거리 구하기
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double dist = calcdist(pos[i].x, pos[i].y, pos[j].x, pos[j].y);
edges.push_back({ dist, i, j });
}
}
sort(edges.begin(), edges.end()); // 오름차순 정렬
for (int i = 0; i < edges.size(); i++) { // MST 구하기
double d = get<0>(edges[i]);
int a = get<1>(edges[i]), b = get<2>(edges[i]);
if (Find(a) == Find(b)) continue;
Union(a, b);
total += d;
}
printf("%.2f", total); // 소숫점 두자리 까지 출력
}
728x90
반응형
'알고리즘 공부 > C++' 카테고리의 다른 글
SWEA 5656번 [모의 SW 역량테스트] 벽돌 깨기 C++ DFS, BFS, 시뮬레이션, 구현 (0) | 2024.08.27 |
---|---|
SWEA 4013번 [모의 SW 역량테스트] 특이한 자석 C++ 덱, 재귀 (0) | 2024.08.27 |
SWEA 1949번 [모의 SW 역량테스트] 등산로 조성 C++ DFS, 완전탐색, 시뮬레이션, 구현 (0) | 2024.08.27 |
백준 3055번 탈출 C++ BFS, 너비 우선 탐색 (0) | 2024.08.26 |
SWEA 2383번 [모의 SW 역량테스트] 점심 식사시간 C++ DFS, 시뮬레이션, 우선순위 큐 (0) | 2024.08.26 |