[G3] 백준 10423번 전기가 부족해 C++ 최소 신장 트리, 유니온-파인드, 정렬

 

리뷰

 

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

오랜만에 풀어본 MST문제, 이미 그룹화 된 정보가 주어졌을 때의 MST의 기본적인 문제이다.

 

 

전역 변수

• n : 도시의 개수를 저장할 변수
• m : 설치 가능한 케이블의 수를 저장할 변수
• k : 발전소의 개수를 저장할 변수
• nodes : 그룹화를 저장하기 위한 정수형 배열
• Edge : 간선의 정보를 나타낼 구조체, 현재 노드 cn, 다음 노드 nn, 가중치 w로 정의하며 가중치 기준 오름차순 정렬

 

함수

1. Find

int Find(int a)

 

현재 노드가 어느 그룹에 속해있는지를 찾기 위한 함수

1. 매개변수로 노드 번호 a를 전달받는다.
2. 기저 조건으로 만약 a가 속한 그룹이 a 자신일 경우 a를 리턴해 준다.
3. 아닐 경우 a가 속한 그룹이 최신이 되도록 재귀를 통해 경로 압축을 진행해 준다.

 

2. Union

bool Union(int a, int b)

 

두 노드를 그룹화 하기 위한 함수

1. 매개변수로 노드 번호 a, b를 전달받는다.
2. 정수형 변수 A, B에 Find 함수를 통해 a, b가 속한 그룹을 구해 저장해 준다.
3. A가 B보다 크다면 A, B를 바꿔주어 A가 항상 작도록 변경해 준다.
4. 만약 A와 B가 동일한 그룹에 속해있다면 false를 리턴해 준다.
5. 아니라면 B가 속한 그룹을 A로 변경해 준 뒤 true를 리턴해 준다.

 

문제풀이

1. n, m, k를 입력 받아주고, nodes배열을 자기 자신의 노드 번호를 값으로 받도록 초기화 해준다.
2. 정수형 벡터 val을 초기화 하고, k개의 발전소 번호를 val에 push해준다.
3. val을 오름차순으로 정렬해 준 뒤 모든 발전소를 가장 앞의 번호로 그룹화 해준다.
4. Edge타입의 벡터 edges를 초기화 해주고, m개의 간선 정보를 edges에 push해준다.
5. edges를 오름차순으로 정렬해 주고, 정수형 변수 sum을 0으로 초기화 해준다.
6. edges를 순회하며 Union함수를 통해 그룹화를 진행한다, 그룹이 성사된 경우 sum에 가중치를 더해준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 문제에 발전소의 번호나 노드의 번호가 오름차순으로 주어진다는 보장이 없다.
• 따라서 발전소 번호를 받고 나서나 Union내부에서 Swap을 통해 별도로 로직을 처리해 주었다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n, m, k;
int nodes[1001];
struct Edge {
	int cn, nn, w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

bool Union(int a, int b) {
	int A = Find(a);
	int B = Find(b);
	if (A > B) swap(A, B);
	if (A == B) return false;
	nodes[B] = A;
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	for (int i = 1; i < 1000; ++i) nodes[i] = i;
	
	vector<int> val;
	while (k--) {
		int a; cin >> a;
		val.push_back(a);
	}

	sort(val.begin(), val.end());
	for (int i = 1; i < val.size(); ++i) {
		nodes[val[i]] = val[0];
	}

	vector<Edge> edges;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		edges.push_back({ a, b, c });
	}

	sort(edges.begin(), edges.end());

	int sum = 0;
	for (const Edge& edge : edges) {
		if (Union(edge.cn, edge.nn)) sum += edge.w;
	}
	cout << sum;
}