[백준] 1774번 우주신과의 교감

문제: 1774번: 우주신과의 교감

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더

using namespace std;

vector<int> nodes; // 정점이 속한 집합 번호
vector<pair<int, int>> coordinates; // 황선자와 우주신들의 좌표

struct compare {
	bool operator()(pair<pair<int, int>, double> a, pair<pair<int, int>, double> b) {
		return a.second > b.second;
	}
};

// 각 정점이 속한 집합 번호 리턴
int find_set(int u) {
	if (nodes[u] == u)
		return u;
	return nodes[u] = find_set(nodes[u]);
}

// 이미 밖에서 연결 여부 확인하고 들어온 거니까 여기서는 그냥 연결만..
void union_(int ur, int vr) {
	nodes[vr] = ur;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m; // n: 우주신들의 개수, m: 이미 연결된 신들과의 통로 개수
	cin >> n >> m;

	nodes = vector<int>(n); // 황선자를 포함한 우주신들의 정점
	for (int i = 0; i < n; i++)
		nodes[i] = i;

	coordinates = vector<pair<int, int>>();
	for (int i = 0; i < n; i++) {
		// 현재 인덱스가 정점의 번호와 같음..
		// 0번 정점의 좌표를 알고싶다? coordinates[0] 의 요소를 가져오면 됨.

		int x, y; // 황선자와 우주신들으 좌표
		cin >> x >> y;
		pair<int, int> coordinate = make_pair(x, y);
		coordinates.push_back(coordinate);
	}

	int selectedEdge = 0; // 이미 선택된 간선 개수
	// 이미 연결되어 있는 통로들 주어짐.
	for (int i = 0; i < m; i++) {
		int u, v; // 이미 연결되어 있는 노드의 정점 번호
		cin >> u >> v;
		u--, v--; // 정점 번호 0부터 시작하도록 만들어가지고,, 이와 마추기 위해 값 조정 해주기..

		// 연결해주면 됨
		// 물론 다른 집합에 속한 상태일때만!
		int ur = find_set(u);
		int vr = find_set(v);
		if (ur != vr) {
			union_(ur, vr); // 연결!
			selectedEdge++; // 이미 선택된 간선 개수 + 1
		}
	}

	// 가중치를 기준으로 최소힙으로 동작하는 우선 순위 큐 만들기(간선 저장)
	// 두번째 요소를 기준으로 최소힙 만들기 위해, 사용자 정의 함수 객체 commpare 만들었다.
	priority_queue<pair<pair<int, int>, double>, vector< pair<pair<int, int>, double>>, compare> edges;

	// 그리고 임의로 모든 점들 사이에 간선을 만들어 놓아야 할 것 같음.
	// 이중반복문 돌아야 하는데 어차피 N 의 최대 범위가 1000까지니까 괜찮아
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) continue; // 음.. 자기 자신이랑은 간선 안 만들어도 되는 거 아닌가

			// 일단 i 정점의 좌표 가져와서 j 정점이랑 거리 계산
			pair<int, int> coord1 = coordinates[i];
			pair<int, int> coord2 = coordinates[j];
			double distance = pow((coord1.first - coord2.first), 2) + pow((coord1.second - coord2.second), 2);
			distance = sqrt(distance);

			// 간선 만들기
			pair<pair<int, int>, double> edge = make_pair(make_pair(i, j), distance);
			edges.push(edge);
		}
	}

	double sum = 0;
	// slectedEdge 값이 (노드개수-1) 보다 작을 때까지 while 문 돌 것..
	while ((selectedEdge < n - 1) && !edges.empty()) {
		pair<pair<int, int>, double> edge = edges.top();
		edges.pop();

		// 이미 두 정점 연결되어 있으면 걍 포기해,,
		int ur = find_set(edge.first.first);
		int vr = find_set(edge.first.second);
		if (ur != vr) {
			union_(ur, vr);
			selectedEdge++;
			sum += edge.second; // 가중치 더해주기
		}
	}
	cout << fixed << setprecision(2) << sum << "\n";


	return 0;
}

 

음.. 바로 어제 푼 문제랑 거의 유사해서 자세히 설명은 안 해도 될 것 같다.

 

일단 이 문제에서는 황선자와 우주신들의 좌표를 제공하고, 이미 연결된 정점들을 알려준다.

 

문제에서 원하는 점은 일단 모든 점을 연결해야 하는데, 통로의 길이가 최소가 되도록 하는 것이다. 즉, 통로의 길이가 최소가 되도록 하려면 각 정점 사이에 가중치로 판단해야 한다. 이 말은 내가 직접 모든 정점 사이에 간선을 만들어줘야 한다.

 

이를 위해서는 이중반복문을 써야하는데 n 의 최대 범위가 1000까지니까 O(n^2) 도 시간초과 없이 잘 돌아갈 것 같다는 판단이 들었다. 그래서 결국 이중반복문 돌면서 각 정점 사이의 간선을 만들어준 후 가중치를 기준으로 최소힙으로 작동하는 우선순위큐에 넣어주었다.

 

이미 선택된 간선의 개수가 n-1 값보다 작을 때까지 while 문을 돌도록 하는게 Kruskal's algorithm 의 핵심이다. 

 

근데 이렇게 풀었는데 4% 까지 맞고 틀렸다고 나왔다. 이유가 대체 뭘까하고 찾아봤는데 각 좌표 사이의 거리를 구해줄 때 공식을 이용해서 직접 구할 때는 거리값을 long long 자료형을 이용해서 저장해야 한다는 것이다..;; 거리 계산할 때 (x1 - x2)를 두 번 곱하는 과정에서 int 형은 자료형의 범위를 벗어나서 에러가 나는 거였다;;;

 

일단 나는 직접 수식으로 계산하지 않고 pow 함수를 쓰는 방법으로 해서 해결하긴 했는데 다음에 직접 수식을 계산하려고 할 때는 x, y 의 범위를 잘 체크해야 겠다는 생각을 했다..

 

그리고 최종 sum 의 자료형도 float 에서 double 로 바꿔줬다.

 

전체적인 로직은 문제 없는데 자료형에서 틀리니까 기분이 너무 안 좋았다. 앞으로 문제 풀 때 자료형 범위를 잘 체크해야 할 것 같다는 생각이 들었다.

 

 

 

참고자료(자료형과 관련된 코드가 잘 짜여있다):

[BOJ] 백준 1774번 : 우주신과의 교감(C++)

[BOJ] 백준 1774번 : 우주신과의 교감(C++)