[C/C++] 백준 14621번 - 나만 안되는 연애

✏️ 문제 링크

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

14621번: 나만 안되는 연애

 

✏️ 문제 설명

 

✏️ 문제 풀이

최소 신장 트리를 구현하는 문제입니다.

기본적인 MST구현 알고리즘에서 조건을 1가지만 추가하면 됩니다.

기존의 MST는 부모 노드가 다르다면 Union을 하지만, 위 문제는 남초대학교와 여초대학교라는 조건이 있습니다.

따라서, Union을 하기 위해서는 두 노드의 학교 성별이 달라야 하고 부모 노드가 달라야 합니다.

 

그리고 주의할 점이 1가지 있습니다. 바로 모든 학교를 연결하는 경로가 없을 때입니다.

보통의 MST문제는 모든 노드를 연결하게 문제를 내주어서(보통 반복문 종료 조건이 사용한 에지 개수 =N-1)그냥 풀면

되지만 이 문제는 모든 학교를 연결하는 경로가 없을수도 있습니다. 따라서 이를 판별해주는 변수 isMST를 만들었습니다.

반복문을 M개만큼 돌리면서 만약 에지의 개수가 N-1이 된다면 isMST=true로 만들고 반복문을 종료시킵니다.

 

✏️ 문제 코드

#include<iostream>
#include<queue>
#include<vector>
#include<set>
using namespace std;

typedef struct Edge {
	int start, end, value;
	bool operator > (const Edge& temp)const {
		return value > temp.value;
	}

}Edge;

int N, M, s, e, v;
vector<char>collage;
vector<int>parent;
set<int>mySet;
void Union(int a, int b);
int find(int a);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	collage.resize(N + 1);
	for (int i = 1; i <= N; i++)
		cin >> collage[i];

	parent.resize(N + 1);
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	priority_queue<Edge, vector<Edge>, greater<Edge>>pq;
	for (int i = 0; i < M; i++) {
		cin >> s >> e >> v;
		pq.push(Edge{ s,e,v });
	}

	int rSum = 0, usedEdge = 0;
	bool isMST = false;
	while (M--) {
		Edge tmp = pq.top();
		pq.pop();
		int start = tmp.start;
		int end = tmp.end;
		int value = tmp.value;
		if (collage[start] != collage[end]) {
			if (find(start) != find(end)) {
				Union(start, end);
				rSum += value;
				usedEdge++;
			}
		}
		if (usedEdge == N - 1) {
			isMST = true;
			break;
		}
	}
	
	if (isMST)
		cout << rSum;
	else
		cout << -1;
}

void Union(int a, int b)
{
	int node1 = find(a);
	int node2 = find(b);

	if (node1 != node2) {
		if (node1 > node2)
			parent[node1] = node2;
		else
			parent[node2] = node1;
	}

}

int find(int a)
{
	if (a == parent[a])
		return a;
	else
		return parent[a] = find(parent[a]);
}

 

 

✏️ 더 보기

https://pooreumjung.tistory.com/326

[C/C++] 백준 다리 만들기 문제 모음 / 백준 2146번, 백준 17472번

https://pooreumjung.tistory.com/332

[C/C++] 백준 10423번 - 전기가 부족해

https://pooreumjung.tistory.com/302

Algorithm 공부 #18 - 그래프(최소 신장 트리)