백준 14621 C++

백준 14621

중요한 점은 모든 대학교가 연결되어야하고, 또한 연결 노선은 다른 성별끼리만 되며, 그 안에서 최단 길이를 구해야한다. 다른 성별끼리만 연결이 가능하다는 점을 제외하면, 익숙하지 않은가? 최소 스패닝 트리(MST)다.

여기서는 간선이 10000개 정도이므로 크루스칼 알고리즘을 사용하면 된다.

크루스칼 알고리즘이니, 두 정점이 연결되어 있지 않은 상태에, 해당 간선을 연결해나간다. 사이클을 이루지 않도록 말이다. 자세한 설명은 코드에 주석으로 남기겠다.

참고로 크루스칼 알고리즘은 Union-Find를 사용하며, 간선의 수는 N - 1개가 되어야만 한다.

#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;

struct info { //시작점, 끝점, 가중치
	int s, e, w;
};
int N, M;
bool gender[1001];
int parents[1001];

vector<info> v1;

int find_parents(int x) {
	if (parents[x] == x) return x;//스스로가 루트 노트일 경우 반환.
	return parents[x] = find_parents(parents[x]); //루트 노드가 아니면 갱신해주고, 반환한다. 
}

void union_parent(int a, int b) {
	a = find_parents(a); //a와 b의 최종 부모를 찾음...
	b = find_parents(b);

	if (a < b) parents[a] = b; //부모가 다를 경우에 합병해준다. 
	else parents[b] = a;
}


bool cmp(info& a, info& b) {
	return a.w < b.w;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;


	for (int idx = 0; idx < N; idx++) {
		char c;
		cin >> c;
		parents[idx + 1] = idx + 1;//간선의 부모를 자신으로 초기화 시켜준다. 
		if (c == 'M') {//들어오는 학교의 성별에 따라 구분을 해준다. 
			gender[idx + 1] = true;
		}
		else {
			gender[idx + 1] = false;
		}
	}
	for (int idx = 0; idx < M; idx++) {
		int s, e, w;
		cin >> s >> e >> w;
		if (gender[s] != gender[e]) {//조건에 성별이 다른 것이 있으니, 성별이 다를 경우에만 간선을 만들어준다. 
			v1.push_back({ s,e,w });
		}
	}
	//Greedy하게 노드를 연결해야 하므로(결국 최단 거리를 구해야 하므로) 가중치가 낮은 순서대로 정렬해준다. 
	sort(v1.begin(), v1.end(), cmp);

	int ans = 0, cnt = 0;

	for (auto const &v : v1) {
		int s = v.s;
		int e = v.e;
		int w = v.w;

		if (find_parents(s) != find_parents(e)) { //s랑 e랑 연결되어 있는지 검사.
			union_parent(s, e);//연결되지 않았을 경우에, 연결해주고.
			ans += w;//가중치를 더해준다.
			if (++cnt == N - 1) { // 간선의 개수가 N - 1 일때, 그 가중치를 출력해준다. 
				cout << ans;
				return 0;
			}
		}
	}
	cout << -1; // N - 1에 미치지 않을 때, 전부 연결이 되지 않은 것이므로 -1 출력. 
	return 0;
}

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