[백준] 4386번 별자리 만들기

문제: 4386번: 별자리 만들기

 

#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> nodes;
vector<pair<float, float>> coordinates; // 좌표값들(좌푤를 노드와 매핑하는데 이용할 것)

// 두 번째 요소인 가중치를 기준으로 최소힙으로 동작하도록 하기 위한 사용자 정의 함수 객체
struct compare {
	// 우선 순위 큐의 디폴트는 최대힙으로 동작
	// 이를 최소힙으로 동작하도록 해주려면 a>b 이를 리턴해줘야함.
	// 근데 지금 두번째 요소를 기준으로 최소힙으로 만드니까 a.second > b.second 이렇게 한 것!!
	bool operator()(pair<pair<int, int>, float>& a, pair<pair<int, int>, float>& 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 vr, int ur) {
	nodes[ur] = vr; // 연결!
}

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

	int n; // 별의 개수
	cin >> n;
	nodes = vector<int>(n); // 노드의 개수는 별의 개수와 같음
	for (int i = 0; i < n; i++)
		nodes[i] = i;

	for (int i = 0; i < n; i++) {
		float x, y; // 별의 좌표
		cin >> x >> y;

		pair<float, float> coordinate = make_pair(x, y);
		// 좌표들 저장하는 벡터에 저장(얘의 0번 인덱스 요소가 0번 노드)
		coordinates.push_back(coordinate); 
	}


	// 간선 저장할 우선 순위 큐(최소힙으로 동작하도록..)
	// 가중치를 기준으로 최소힙으로 동작하도록 하고 싶음..
	// 아 처음에 비교 함수로 함수 포인터를 주려고 했는데 안된대여.. 대신에 비교 함수 객체를 사용해야함.
	// 안되는 이유도 찾아봤는데 c++ 템플릿 시스템이 prioiry_queue 의 비교 정책을 타입으로 받아들임
	// 근데 일반 함수는 타입이 아니니까 템플릿 인자로 바로 전달할 수 없음..
	// 대신 구조체나 클래스를 사용해서 그 안에 operator() 를 오버로딩 하면, 이를 함수 객체로서 전달 가능
	priority_queue<pair<pair<int, int>, float>, vector<pair<pair<int, int>, float>>, compare> edges;

	// 일단 모든 정점들끼리의 간선을 만들어줄 것.
	// 이는 시간복잡도가 O(n**2) 인데 n 의 최대 범위가 100까지니까 괜찮음
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			// 자기 자신이랑은 거리 계산할 필요 없는거 아님?
			if (i == j) continue;

			pair<float, float> a = coordinates[i]; // 좌표 1
			pair<float, float> b = coordinates[j]; // 좌표 2

			// 두 좌표의 거리 계산
			float distance = sqrt(((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)));
			pair<pair<int, int>, float> edge = make_pair(make_pair(i, j), distance); // 정점이랑 가중치를 묶어서 간선 저장 최소힙에 저장
			edges.push(edge); // 힙에 넣어용..
		}
	}

	int edgeCnt = 0; // 이 값이 (노드 개수 - 1) 보다 작을때까지 반복문 돌 것..
	float sum = 0;
	while (edgeCnt < (n - 1) && !edges.empty()) {
		pair<pair<int, int>, float> minEdge = edges.top();
		edges.pop(); // 꺼내야 하니까 pop 해주기

		// 정점이 이미 연결되어 있는데 또 연결하려고 하면 사이클이니까 이 경우는 패스!
		int ur = find_set(minEdge.first.first);
		int vr = find_set(minEdge.first.second);
		if (ur != vr) {
			union_(ur, vr); // 연결
			sum += minEdge.second; // 가중치 더해주기..
			edgeCnt++;
		}
	}
	cout << sum << "\n";

	return 0;
}

 

우선 어제 풀었던 1197번과 다른 점은 입력이 정점 번호가 아니라 좌표값으로 들어온다는 점과, 가중치를 직접 주던 전과는 다르게 직접 계산을 해줘야 한다는 것이다.  그리고 1197번은 각 정점 사이의 간선 정보도 주었는데 이를 주지 않아서 간선도 직접 만들어줘야 했다.

 

각 정점을 다른 모든 정점과 연결해 줘도 되겠다는 생각을 한 건 입력 조건을 보고 난 후였다. 일단 지금 별의 개수인 n 의 최대 범위가 100밖에 안 되므로 다른 모든 정점과 연결해줘도(시간복잡도 O(n^2)) 시간이 충분하겠다는 판단이 들었다.

 

그리고 이 문제의 또 중요한 점은 입력 받은 좌표를 정점 번호로 매핑해줘야 한다는 것인데 간단하게 해결할 수 있다. 일단 coordinates 라는 좌표값들을 저장할 벡터를 하나 만들었다. 이는 좌표를 노드와 매핑하는데 이용하는데 사용법은 다음과 같다. 그냥 단순히 coordinates 벡터의 0번째 요소가 0번 정점이라고 생각하는 것이다.

 

이제 또 중요한 점은 간선들을 저장해놓을 우선 순위 큐를 만드는 것이었다. 일단 최소힙으로 동작해야 하고, pair 의 두번째 요소인 가중치를 기준으로 최소힙을 만들고 싶었다. 이를 위해서 처음에 compare 라는 함수를 만들어서 priority_queue 의 비교 함수로 전달하려고 했는데 실패했다. 이유는 우선 순위 큐의 비교 함수로 함수 포인터를 주는게 불가능해서...

대신에 비교 함수 객체를 사용하면 됐다. 그래서 기존에 만들었던 compare 함수 대신에 struct 로 만들고, operator() 를 오버로딩 해서 똑같은 기능을 하도록 만들었다.

 

이중 반복문을 돌면서 좌표 1과 좌표 2 사이의 거리를 계산했다. 이는 가중치를 의미한다. 아까 말했던 것처럼 coordinates 의 인덱스가 곧 정점 번호를 의미한다. 그래서 간선을 만들 때, pair<int, int> 정점 번호의 쌍으로 현재 for 문 당시의 인덱스 번호를 넘겨주었다. 

 

모든 간선들을 저장하고 난 다음에는 기존에 하던 방식대로 해결하면 된다. 현재까지 선택된 간선의 개수가 (노드의 개수 - 1) 보다 작을 때까지 반복문을 돌도록 하고, 각 반복문 마다 최소 간선을 하나 꺼낸다음 이 간선의 두 정점이 이미 연결되어 있는지 여부를 판단하고, 아니라면 연결해준다음 가중치를 sum 값에 더해주면 쉽게 해결할 수 있다.

 

재밌었다 ^0^

 

 

 

참고자료:

[C언어/C++] pow, sqrt 함수에 대해서(루트함수, 제곱, 제곱근)

[C언어/C++] pow, sqrt 함수에 대해서(루트함수, 제곱, 제곱근)