[G3] 백준 14621번 나만 안되는 연애 C++ 최소 스패닝 트리, MST, 크루스칼 알고리즘, 유니온 파인드

리뷰

 

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

간만에 풀어본 MST문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• gender : 성별을 저장할 배열
• group : 속한 그룹의 번호를 저장할 배열
• Edge : 간선 정보를 정의할 구조체, 간선의 가중치를 기준으로 오름차순 정렬한다.
• edges : 간선 정보를 저장할 Edge타입 벡터

 

함수

1. Find

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

 

현대 노드가 속한 그룹의 번호를 반환하고, 경로 압축을 실행하기 위한 함수

 

2. Union

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

 

두 노드가 같은 그룹에 속해있지 않으면 두 그룹을 합치기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, n개 노드의 성별에 따라 gender배열을 초기화한다.
2. m개의 간선 정보를 입력 받고, 같은 성별이 아닐 경우 간선을 edges에 추가한다.
3. sort함수를 통해 edges벡터를 가중치를 기준으로 오름차순 정렬한다.
4. 1~n번 노드의 초기 그룹 번호를 자기 자신이 되도록 초기화한다.
5. 변수 sum, cnt를 0으로 초기화하고, edges벡터를 순회한다.
6. 매 루프마다 변수 f, t, w에 두 노드와 가중치를 저장한다.
7. Union함수에 f, t를 매개변수로 전달하여 호출하고, 반환값이 true라면 sum에 w를 더하고 cnt를 증가시킨다.
8. 최종적으로 cnt가 n-1일경우 sum을 출력하고, 아니라면 -1을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 사심 경로는 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있으므로 성별이 같은 경우 간선을 edges벡터에 추가하지 않았다.

 

정답 코드

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

const int N = 1001;
int n, m;
bool gender[N];
int group[N];
struct Edge {
	int f, t, w;
	bool operator<(const Edge& other) const {
		return w < other.w;
	}
};
vector<Edge> edges;

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

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

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

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		char c; cin >> c;
		if (c == 'W') gender[i] = true;
	}

	while (m--) {
		int f, t, w; cin >> f >> t >> w;
		if (gender[f] == gender[t]) continue;
		edges.push_back({ f, t, w });
	}
	sort(edges.begin(), edges.end());

	for (int i = 1; i <= n; ++i) group[i] = i;

	int sum = 0, cnt = 0;
	for (const Edge& edge : edges) {
		int f = edge.f, t = edge.t, w = edge.w;
		if (Union(f, t)) {
			sum += w;
			++cnt;
		}
	}
	cout << (cnt == n - 1 ? sum : -1);
}