알고리즘 공부/C++

백준 1774번 우주신과의 교감 C++ MST, 최소 신장 트리

마달랭 2024. 8. 27. 16:55
반응형

리뷰

double 조심! int 오버플로우 조심!

각 노드의 좌표가 주어지고 모든 노드를 연결하는 최소값을 구하는 문제

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

 

문제 풀이

  1. n과 m 값을 받아오고 각 노드의 좌표를 구조체 배열로 받아오고, 자신의 인덱스를 value로 갖는 nodes 배열을 초기화
  2. m줄에 걸쳐 이미 연결되어 있는 노드들 끼리는 Union 처리를 해준다.
  3. 모든 노드들 간의 간선을 edges 벡터에 저장해 준다. 이때 각 간선의 거리를 구해주어야 한다.
  4. 간선의 거리를 기준으로 오름차순 정렬해 준 후 모든 노드가 연결 되도록 부분 집합을 활용해 연결해 준다.
  5. 각 간선이 연결 될때마다 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
반응형