백준 1043 (거짓말) c++

문제

1043번: 거짓말

n개의 사람수와 m개의 파티수가 주어집니다.

그 다음 진실을 아는 사람의 수와 진실을 아는 사람들의 번호가 주어집니다.

또한 진실을 아는 사람과 파티에 참석하면 나머지 사람들도 진실을 알게 됩니다.

그 다음 m개의 줄에 파티를 참여하는 수와 파티를 참여하는 사람들의 번호가 m개의 줄에 주어집니다.

이 때 진실을 아는 사람의 눈을 피해 거짓말을 할 수 있는 파티의 개수의 최댓값을 구하는 문제입니다.

 

예를 들어

3 4
1 3
1 1
1 2
2 1 2
3 1 2 3

n = 3, m = 4 이고 진실을 아는 사람은 1명이고 그 사람의 번호는 3이고

m개의 줄에 파티의 정보가 주어집니다.

맨 마지막 파티에 진실을 아는 3번과 함께이므로 거지말을 할 수 있는 파티의 갯수는 0입니다.

 

제가 처음에 접근한 방법은 

진실을 아는 사람들을 map 자료구조에 넣어 새로운 파티가 입력될 때 마다 map에 있는 사람들과 비교해

거짓말을 할 수 있는 파티의 갯수를 세어주는 것입니다.

하지만 그렇게 되면 위에 있는 예시처럼 마지막에 진실을 아는 사람과 마주쳤을 때는 지금까지 세어준

파티의 갯수가 무요지물이 되어 셀 수 가 없습니다.

 

먼저 이를 해결하기 위해 생각한 방법은 마지막 입력까지 결과에 영향을 줄 수 있기 때문에

입력 하나하나 들어올 때 마다 파티를 세는 것이 아닌

모든 입력이 다 들어오고 파티를 세는 방법을 택했습니다.

 

이를 위해 Union-Find 알고리즘을 생각해볼 수 있습니다.

다음과 같이 진실을 아는 번호는 빨간색으로 표시해 주었습니다.

그럼 이제 입력을 모두 받은 파티를 union 해보겠습니다.

왼쪽 처럼 union 되고 결국 오른쪽 처럼 모두 진실을 알게 됩니다.

결국 진실을 아는 번호와 그렇지 않은 번호의 parent가 같게 되면 이는 진실을 아는 번호가 되므로

진실을 아는 번호와 그렇지 않은 번호의 parent가 다른 것만 찾게 되면 정답이 됩니다.

int vilain;
cin >> vilain;

for (int i = 0; i < vilain; i++) {
	int a;
	cin >> a;
	know.push_back(a);
}

먼저 진실을 아는 사람을 입력 받아 know 벡터에 모두 넣어 줍니다.

for (int i = 1; i <= n; i++)parent[i] = i;

그 다음 처음에 모든 parent 배열을 해당 번호로 초기화 해줍니다.

vector<int>v[51];

for (int i = 0; i < m; i++) {
	int a;
	cin >> a;
	int x, y;
	for (int j = 0; j < a; j++) {
		if (j >= 1) {
			y = x;
			cin >> x;
			Union(y, x);
		}
		else cin >> x;
		v[i].push_back(x);
	}
}

이제 파티를 입력받는 부분입니다.

각 파티마다 v 벡터에 넣어줍니다.

그리고 파티에 넣어줄 때 마다 서로 union을 해야 하므로 union하고 넣어줍니다.

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

void Union(int x, int y) {
	x = find(x);
	y = find(y);
	parent[x] = y;
}

union하고 find 함수입니다. 이전에 배웠던 함수와 똑같습니다.

for (auto nxt : v) {
	bool chk = false;
	for (auto nxt1 : nxt) {
		if (chk)break;
		for (auto x : know) {
			if (find(nxt1) == find(x)) {
				chk = true;
				break;
			}
		}
	}
	if (chk)m--;
}
cout << m;

for문이 많아 복잡해 보이지만 차근차근 보면 매우 쉽습니다.

먼저 각각의 파티가 입력된 v벡터부터 시작합니다.

그럼 각각의 파티마다 아까 처음에 받았던 진실을 알고 있는 know 벡터와 parent를 비교하게 됩니다.

만약 parent가 같으면 진실을 아는 파티에 있던 것이므로 m을 -1을 해주고 이를 계속 반복해줍니다.

마지막에 m을 출력해주면 정답이 됩니다.

 

union-find 알고리즘을 배우긴 했지만 문제로 접해본것은 이번이 처음이었습니다.

좋은 문제라고 생각합니다.

---

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
map<int, int>vi;
vector<int>know;
int parent[51];
vector<int>v[51];
int find(int x);
void Union(int x, int y);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n, m;
	cin >> n >> m;

	int vilain;
	cin >> vilain;
	for (int i = 0; i < vilain; i++) {
		int a;
		cin >> a;
		know.push_back(a);
	}
	for (int i = 1; i <= n; i++)parent[i] = i;
	
	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		int x, y;
		for (int j = 0; j < a; j++) {
			if (j >= 1) {
				y = x;
				cin >> x;
				Union(y, x);
			}
			else cin >> x;
			v[i].push_back(x);
		}
	}
	
	for (auto nxt : v) {
		bool chk = false;
		for (auto nxt1 : nxt) {
			if (chk)break;
			for (auto x : know) {
				if (find(nxt1) == find(x)) {
					chk = true;
					break;
				}
			}
		}
		if (chk)m--;
	}
	cout << m;

	return 0;
}
int find(int x) {
	if (parent[x] == x)return x;
	return x = find(parent[x]);
}
void Union(int x, int y) {
	x = find(x);
	y = find(y);
	parent[x] = y;
}