백준/1043/graph(union_find)/거짓말

백준/1043/graph(union_find)/거짓말

문제 해석

지민이가 파티에서 이야기를 부풀려 하고 싶어합니다. 하지만 이 이야기에 진실을 아는 사람들이 있으면 거짓말쟁이가 되기 때문에 그것을 피해야만 합니다.
이 때 지민이가 이야기를 부풀려 할 수 있는 파티의 최대 수를 구하는 문제입니다.

문제 풀이

우선 생각할 수 있는 풀이는 진실을 아는 사람과 각 파티 인원을 일일이 비교하는 방법입니다. 주어지는 사람수도 적기에 나쁘지 않은 방법이라 생각할 수 있으나, 문제 예제를 보면 파티에 순서가 정해져 있지 않아 주어진 파티에서 진실을 알고 있는 사람이 다른 파티에서 애기할 수도 있다는 점에서 비효율적인 방법이 됩니다.

저는 이 문제를 해결 하기 위해 다음과 같이 풀이 방법을 설계하였습니다.

1. 진실을 알고 있는 사람들의 그룹을 만들어준다. 그룹 표시는 그 그룹의 대표(index가 가장 작은 사람)으로 한다.

• 예외 상황 : 진실을 알고 있는자가 없을 경우 아래에 연산들을 불필요하고, 답은 무조건 주어진 파티의 수가 된다.

2. 이 후 파티에 참석한 인원들 역시 그룹을 지어가면서 이 사람 중에서도 진실을 알고 있는 사람들과 같은 파티에 참석했다면 같은 그룹으로 지어준다.
3. 진실을 알고 있는 그룹의 대표 인덱스를 찾고, 그 대표 인덱스를 활용해 각 파티의 참여한 사람들의 대표 그룹 인덱스와 비교한다.
4. 대표 그룹 인덱스가 진실을 알고 있는 그룹의 대표 인덱스와 같은 사람이 하나라도 있을 경우 해당 파티 수는 제외한다.

그룹 짓기 및 대표 그룹 인덱스 찾는 function

int find_parent(int num)
{
	if (parent[num] == num)return num;
	return parent[num] = find_parent(parent[num]);
}

void union_make(int u, int v)
{
	u = find_parent(u); v = find_parent(v);
	if (u == v)return;
	if (u < v)parent[v] = u;
	else parent[u] = v;
}

1. 진실을 알고 있는 사람들의 그룹을 만들어준다. 그룹 표시는 그 그룹의 대표(index가 가장 작은 사람)으로 한다.

// N은 사람의 수, M은 파티의 수
int N, M = 0;

// 과장된 이야기를 할 수 있는 파티 수
int result = 0;

cin >> N >> M;

for (int i = 1;i <= N;i++)
{
	parent[i] = i;
}

bool flag = false;
int prev = 0;
int true_person = 0;
int true_person_find_index = 0;
cin >> true_person;

for (int i = 0;i < true_person;i++)
{
	int _true_person_index = 0;
	cin >> _true_person_index;
	true_group.push_back(_true_person_index);
	if (!flag)
	{
		true_person_find_index = _true_person_index;
		prev = _true_person_index;
		flag = true;
	}
	else
	{
    	// 진실을 알고 있는 사람 그룹 만들기
		union_make(prev, _true_person_index);
		prev = _true_person_index;
	}
}

for (int _person:true_group)
{

	// 해당 그룹의 대표번호를 가지게끔 재탐사
	find_parent(_person);
}

2. 이 후 파티에 참석한 인원들 역시 그룹을 지어가면서 이 사람 중에서도 진실을 알고 있는 사람들과 같은 파티에 참석했다면 같은 그룹으로 지어준다.

v.resize(M);

for (int i = 0;i < M;i++)
{
	int prev = 0;
	bool _first_flag = true;
	int _person_count = 0;
	cin >> _person_count;
	for (int j = 0;j < _person_count;j++)
	{
		int _party_person_index = 0;
		cin >> _party_person_index;

		v[i].push_back(_party_person_index);
		if (_first_flag)
		{
			prev = _party_person_index;
			_first_flag = false;
		}
		else
		{
			union_make(prev, _party_person_index);
			prev = _party_person_index;
		}
	}
}

for (int i = 0;i < M;i++)
{
	for (int _person : v[i])
	{
		find_parent(_person);
	}
}

// 진실을 알고 있는 사람 그룹 대표 인덱스
int compared_value = parent[true_person_find_index];

3. 진실을 알고 있는 그룹의 대표 인덱스를 찾고, 그 대표 인덱스를 활용해 각 파티의 참여한 사람들의 대표 그룹 인덱스와 비교한다.
4. 대표 그룹 인덱스가 진실을 알고 있는 그룹의 대표 인덱스와 같은 사람이 하나라도 있을 경우 해당 파티 수는 제외한다.

for (int i = 0;i < M;i++)
{
	bool _flag = true;
	for (int _person : v[i])
	{
		if (parent[_person] == compared_value)
		{
        	// 이럴 경우 파티에 참가한 인원중 한명이라도 진실을
            // 아는 사람이 존재하는 경우이니 _flag를 false로 만들어줌
			_flag = false;
		}
	}
	
    // 한 사람도 진실을 알고 있지 않은 파티이므로 result 값 증가
	if (_flag)
	{
		result++;
	}
}

if (true_person == 0)
{
	cout << M << '\n';
}
else
{
	cout << result << '\n';
}

풀이

첫번째 풀이

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

// 사람과 파티의 수 각각 50이하
int parent[51];
vector<vector<int>>v;
vector<int>true_group;

int find_parent(int num)
{
	if (parent[num] == num)return num;
	return parent[num] = find_parent(parent[num]);
}

void union_make(int u, int v)
{
	u = find_parent(u); v = find_parent(v);
	if (u == v)return;
	if (u < v)parent[v] = u;
	else parent[u] = v;
}

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

	// N은 사람의 수, M은 파티의 수
	int N, M = 0;

	// 과장된 이야기를 할 수 있는 파티 수
	int result = 0;

	cin >> N >> M;

	for (int i = 1;i <= N;i++)
	{
		parent[i] = i;
	}

	bool flag = false;
	int prev = 0;
	int true_person = 0;
	int true_person_find_index = 0;
	cin >> true_person;

	for (int i = 0;i < true_person;i++)
	{
		int _true_person_index = 0;
		cin >> _true_person_index;
		true_group.push_back(_true_person_index);
		if (!flag)
		{
			true_person_find_index = _true_person_index;
			prev = _true_person_index;
			flag = true;
		}
		else
		{
			union_make(prev, _true_person_index);
			prev = _true_person_index;
		}
	}

	for (int _person:true_group)
	{
		find_parent(_person);
	}

	v.resize(M);

	for (int i = 0;i < M;i++)
	{
		int prev = 0;
		bool _first_flag = true;
		int _person_count = 0;
		cin >> _person_count;
		for (int j = 0;j < _person_count;j++)
		{
			int _party_person_index = 0;
			cin >> _party_person_index;

			v[i].push_back(_party_person_index);
			if (_first_flag)
			{
				prev = _party_person_index;
				_first_flag = false;
			}
			else
			{
				union_make(prev, _party_person_index);
				prev = _party_person_index;
			}
		}
	}

	for (int i = 0;i < M;i++)
	{
		for (int _person : v[i])
		{
			find_parent(_person);
		}
	}

	int compared_value = parent[true_person_find_index];

	for (int i = 0;i < M;i++)
	{
		bool _flag = true;
		for (int _person : v[i])
		{
			if (parent[_person] == compared_value)
			{
				_flag = false;
			}
		}

		if (_flag)
		{
			result++;
		}
	}

	if (true_person == 0)
	{
		cout << M << '\n';
	}
	else
	{
		cout << result << '\n';
	}

	return 0;
}