[BOJ] 14621번 나만 안되는 연애 (C++)

문제 (https://www.acmicpc.net/problem/14621)

14621번: 나만 안되는 연애

최소 스패닝 트리 문제이다. 크루스칼 알고리즘을 사용해서 해결했다.

특별히 어려운 점은 없는데 처리해야 할 조건이 하나 있다.

 

남초-남초, 여초-여초로 연결되면 안 되고 항상 번갈아가면서 연결되어야 한다. 따라서 나는 두 노드를 union 하기 전, 두 노드의 성별이 다른지 확인했다.

만약 해당 조건이 없다면 위 그래프의 답은 3(CD) + 5(BD) + 5(BE) + 10(AC) = 23이 될 것이다. 하지만 조건에 의해 오른쪽 사진과 같은 결과가 나온다.

 

만약 모든 학교를  연결하는 경로가 없을 경우 -1을 출력해야 한다. 두 노드가 union이 될 때마다 카운팅을 하여 카운트 수가 n - 1보다 작다면 -1을 출력하도록 했다.

---

[소스코드]

	/*
	BOJ 14621번: 나만 안되는 연애
	DATE: 2022-03-03
	Kruskal Algorithm
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#define MAX 1001
	using namespace std;
	char gender[MAX];
	vector<pair<int, pair<int,int>>> edge;
	int parent[MAX];
	int getParent(int x){
	if(x == parent[x]) return x;
	return parent[x] = getParent(parent[x]);
	}
	int findParent(int a, int b){
	a = getParent(a);
	b = getParent(b);
	if(a == b) return 1;
	else return 0;
	}
	void unionParent(int a, int b){
	a = getParent(a);
	b = getParent(b);
	if(a < b) parent[b] = a;
	else parent[a] = b;
	}
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m, ans = 0, cnt = 0;
	int a, b, c;
	char ch;
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i++) cin >> gender[i];
	for(int i = 0 ; i < m ; i++){
	cin >> a >> b >> c;
	edge.push_back({c, {a, b}});
	}
	sort(edge.begin(), edge.end());
	for(int i = 1 ; i <= n ; i++) parent[i] = i;
	for(int i = 0 ; i < edge.size() ; i++){
	int x = edge[i].second.first;
	int y = edge[i].second.second;
	int z = edge[i].first;
	if(gender[x] != gender[y] && !findParent(x, y)){
	unionParent(x, y);
	ans += z;
	cnt++;
	}
	}
	if(cnt < n - 1) cout << -1;
	else cout << ans;
	return 0;
	}

view raw 14621.cpp hosted with ❤ by GitHub

---

2022-03-03

Gold 3

- 그래프 이론

- 최소 스패닝 트리