백준 Gold 3 나만 안되는 연애

나만 안되는 연애 (백준 Gold 3)

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

각 대학교를 엮는 도로를 만들되
다음과 같은 규칙을 만족해야 하는 문제

• 남학교와 여학교만을 연결해야 함
  
• 어떤 대학이든 도로가 연결되어야 함
  
• 결과적으로 최단 거리가 되어야 함
  

풀이 방법

모든 노드를 연결하는 최단 거리와 관련된 문제이므로
MST 계열의 문제이다

다만, 서로 같은 성별비의 학교라면
도로를 짓지 못하기에

임의의 구조체를 이용하여
FindParent와 Union을 구현하면 풀 수 있다

제출 코드

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

using namespace std;

struct nodeData
{
	int parent;
	bool bMan;
};

int FindParent(vector<nodeData>& pv, int x)
{
	if (pv[x].parent == x)
		return x;

	return pv[x].parent = FindParent(pv, pv[x].parent);
}

bool Union(vector<nodeData>& pv, int a, int b)
{
	if (pv[a].bMan == pv[b].bMan)
		return false;

	a = FindParent(pv, a);
	b = FindParent(pv, b);

	if (a == b)
		return false;

	pv[a].parent = b;

	return true;
}

struct edge
{
	int s, t, cost;
};

int main()
{
	int n, m;
	cin >> n >> m;

	vector<nodeData> pv(n);
	vector<edge> ev(m);

	for (int i = 0; i < n; i++)
	{
		char c;
		cin >> c;
		if (c == 'M')
			pv[i].bMan = true;
		else
			pv[i].bMan = false;

		pv[i].parent = i;
	}

	for (int i = 0; i < m; i++)
	{
		cin >> ev[i].s >> ev[i].t >> ev[i].cost;
		ev[i].s--;
		ev[i].t--;
	}

	sort(ev.begin(), ev.end(), []
	(const auto& a, const auto& b)
		{
			return a.cost < b.cost;
		});


	int ans = 0;
	int count = 0;

	for (edge& e : ev)
	{
		if (Union(pv, e.s, e.t))
		{
			ans += e.cost;
			count++;
		}
	}

	if (count == n - 1)
		cout << ans;
	else
		cout << -1;

	return 0;
}

결과

마지막에 연결할 수 없는 경우에 대한 출력 -1 에 대한 부분을 놓쳐
처음에는 오답처리를 받았다
이후 수정하여 해결