[백준 1774][💛4] 우주신과의 교감 (MST)

🚀 난이도

💛 골드 4

🚀 문제

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

🚀 내 풀이 ⭕

문제의 예제로는 이런 상태인 것! 빨간 선은 이미 연결 되어 있는 상태를 뜻하고 파란건 모든 우주신을 연결하기 위해 최소 길이의 연결 통로를 놓은 모습이다.

총합 최소 길이의 연결 통로를 놔서 우주신을 모두 연결할 수 있도록 하는 것! 딱 최소 신장 트리의 문제이다. 우주신 하나 하나를 정점으로 생각해 본다면, 최소로 간선들을 연결해서 모든 정점을 하나의 트리에 속하도록 연결 시키는 문제와도 같기 때문이다. MST 알고리즘 중 하나인 크루스칼 알고리즘을 사용하여 모든 우주신을 최소 연결 통로로 연결해보자.

주의해야할 점이 있다면, 이 문제에서는 딱히 간선이 담긴 어떠한 리스트를 제공하지 않는다. 그렇기 때문에 각 우주신의 좌표를 연결지을 수 있는 nC2 개의 모든 간선을 구해놓아야 한다.

1. 우주신의 좌표들끼리의 길이를 모두 구한다. (nC2 개의 간선이 나올 것)
2. 우주신들끼리의 nC2 개의 간선을 오름차순 정렬한다.
3. 정렬을 했으니 최소 길이의 간선부터 연결시킨다.

#include <bits/stdc++.h>

using namespace std;

struct Pos { int x, y; };
struct Edge { int num1, num2; double cost; }; // num1 우주신과 num2 우주신 사이의 연결 통로. 세 개의 데이터를 묶을 수 있도록 구조체 선언함.
vector<int> parent;
 
// a 정점의 부모가 누구인지. (즉, a 가 현재 속해있는 트리의 루트 리턴)
// 그와 동시에 만약 이 함수를 호출하기 전인 사전에 루트의 부모가 바뀌었다면(즉, 다른 그래프에 속하도록 병합되었다면) 그것에 대한 자식들 수정까지 모두 이루어질 수 있도록 재귀 호출에서 대입 연산도 해준다. 
int getParent(int a) {
	if (a == parent[a]) return a;
	return parent[a] = getParent(parent[a]);
}

// 두 그래프 병합 (루트가 더 작은 쪽으로 병합하기로 함)
// 병합되는쪽의 루트의 부모를 바꿔주면 된다. 
void connect(int a, int b) {
	int par_a = getParent(a);
	int par_b = getParent(b);
	if (par_a < par_b) parent[par_b] = par_a;
	else parent[par_a] = par_b;
}

// 같은 그래프에 속해있는지
bool isConnected(int a, int b) {
	int par_a = getParent(a);
	int par_b = getParent(b);
	if (par_a == par_b) return true;
	else return false;
}

bool cmp(const Edge& a, const Edge& b) {
	return a.cost < b.cost;
}

double getDistance(Pos pos1, Pos pos2) {
	return sqrt(pow((pos1.x - pos2.x), 2) + pow((pos1.y - pos2.y), 2));
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M;
	cin >> N;
	cin >> M;
	vector<Pos> pos(N + 1);
	for (int i = 1; i <= N; ++i) {
		cin >> pos[i].x;
		cin >> pos[i].y;
	}
	vector<pair<int, int>> connected(M);
	for (int i = 0; i < M; ++i) {
		cin >> connected[i].first;
		cin >> connected[i].second;
	}

    // 1. 두 우주신 간의 거리를 모두 구한다. 즉 nC2 개의 간선 구해서 edges 배열에 저장!  
    // nC2 조합 구하는게 아래와 같이 되는 이유는.. [1,2,3,4] 의  2개 뽑는 조합은 (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) 이 된다는 것을 생각하면 이해할 수 있을 것이다. 
	vector<Edge> edges;
	for (int i = 1; i <= N - 1; ++i)
		for (int j = i + 1; j <= N; ++j)
			edges.push_back({ i, j, getDistance(pos[i], pos[j]) });
	// 2. 정렬 (거리 별 정렬)
    sort(edges.begin(), edges.end(), cmp);

    // 3. 오름차순 정렬 되었으니 최소 간선부터 연결 (단, 부모가 같지 않은 노드만 연결. 즉 같은 그래프에 속해있지 않은 것만) 
	parent.resize(N + 1);
	for (int i = 1; i <= N; ++i)
		parent[i] = i;
	for (int i = 0; i < M; ++i)
		connect(connected[i].first, connected[i].second); // 문제에서 주어진, 이미 연결되어 있다는 우주신들 연결 처리
	double connect_cost = 0.0f;
	for (int i = 0; i < edges.size(); ++i) {
		if (isConnected(edges[i].num1, edges[i].num2) == false) {
			connect(edges[i].num1, edges[i].num2);
			connect_cost += edges[i].cost;
		}
	}

    // 4. 소수점 둘째자리까지 출력하도록
	cout << fixed;
	cout.precision(2);
	cout << connect_cost;
}

내 자신에게 남기는 주의사항

	double connect_cost = 0.0f;
	for (int i = 0; i < edges.size(); ++i) {
		if (isConnected(edges[i].num1, edges[i].num2) == false) {
			connect(edges[i].num1, edges[i].num2);
			connect_cost += edges[i].cost;
		}
	}

굳이 매 반복마다 모든 정점이 다 연결되었는지 확인하지 않아도 된다. 매 반복마다 모든 정점이 다 연결되었는지 확인하려면 또 그자체로 반복문을 돌려야 하기에 이중 for 문이 되는 셈이다. 굳이 그러지 않아도 된다. 왜냐하면 어차피 모든 정점이 연결이 다 되어 하나의 그래프가 되었다면 그 뒤로는 절대 if (isConnected(edges[i].num1, edges[i].num2) == false) 에 걸리지 않기 때문이다. 그러니 굳이 시간복잡도 높여서 모든 정점이 다 연결되었는지 확인할 필요가 없다.

모든 정점이 연결 되었을 때 더 이상 for문 돌리지 않고 break 시키고 싶다면, 연결된 정점의 개수를 따로 카운팅하고 이게 N 과 같아졌는지를 검사하면 될 것이다! 굳이 검사를 한다면 이렇게…

(내가 처음에 떠올린 생각은 모든 노드를 일일이 연결되었는지 검사를 해야하나..?라는 것이였기 때문에 남기는 메모이다.)

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기