백준 1043 거짓말 (c++) : 피너클

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

1043번: 거짓말

유니온 파인드를 이용한 문제다.

한번 진실을 말하면 그 진실을 들은 사람이 있는 모든 파티에서 거짓말을 할 수 없다.

파티안에 진실을 들은 사람이 있는지를 확인해야한다.

int n, m, k;
int uni[51];
bool know[51];
vector<int> party[51];

uni는 사람끼리의 관계를 나타날때 사용한다. 어느 사람이 어디까지 연관되어 있는지를 알수있다.

know는 진실을 아는 사람을 나타낸다.

int find(int num) {
	if (uni[num] == num) return num;
	return find(uni[num]);
}

find함수다. 전달받은 사람의 최초 조상이 누군지 알수있다.

cin >> n >> m;
for (int i = 1; i <= n; i++) uni[i] = i, know[i] = false;
cin >> k;

먼저 값들을 입력받으녀 uni와 know를 세팅한다.

int mi = -1;
for (int i = 0; i < k; i++) {
	int a;
	cin >> a;
	if (mi == -1) {
		mi = a;
	}
	uni[a] = mi;
	know[a] = true;
}

그후 진실을 아는 사람들을 입력받는다.

이때 처음 진실을 아는 사람이 최초 조상이 된다.

1, 3, 5, 7이 입력된다면 최초 조상은 1이되고 uni[1], uni[3], uni[5], uni[7]에는 1이 들어간다.

만약 find(7)을 한다면 uni[7] -> uni[1] 에서 1이 반환될것이다.

for (int i = 0; i < m; i++) {
	int a;
	cin >> a;
	for (int j = 0; j < a; j++) {
		int b;
		cin >> b;
		party[i].push_back(b);
	}
	sort(party[i].begin(), party[i].end());
}

그후 파티들을 입력받은뒤 정렬한다.

이제 계속 파티들을 돌아보며 갱신할것이다. 만약 갱신할것이 없다면 반복문에서 빠져나온다.

int last = -1;
while (1) {
	int minus = 0;

last는 이전에 반복문을 돌렸을때 몇개의 파티에서 진실을 말할수 없는지의 숫자를 나타낸다.

minus는 이번 반복문에서 몇개의 파티에서 진실을 말할수 없는지의 숫자를 나타낸다.

	for (int i = 0; i < m; i++) {
		bool chk = false;
		for (int j = 0; j < party[i].size(); j++) {
			if (know[find(party[i][j])]) {
				chk = true;
				break;
			}
		}

모든 파티를 한번씩 돌아본다. chk는 이 파티에서 진실을 말할수 없는지를 확인한다. true면 말 못한다.

파티 인원을 보며 파티 인원의 최초 조상이 (find(party[i][j])) 진실을 알고 있다면 chk=true로 바꾸고 반복문을 나온다.

		if (chk) {
			minus++;
			know[find(uni[party[i][0]])] = true;
			for (int j = 0; j < party[i].size(); j++) uni[party[i][j]] = find(uni[party[i][0]]);
		}
	}

만약 현재 파티에서 거짓말을 할 수 없다면

먼저 minus++를 한뒤

첫번째 파티 참가자의 최초 조상의 know를 true로 바꾸고

for문을 통해 모든 파티 참가자의 최초 조상을 첫번째 파티 참가자의 최초 조상으로 바꾼다.

이것이 파티를 입력받았을때 정렬한 이유다.

	if (last != -1 && last == minus) {
		m -= minus;
		break;
	}
	last = minus;
}
cout << m << endl;

 

 

 

그후 last가 -1이 아니고 (반복문을 처음 돌렸을때는 last가 -1이다.) last == minus라면 (이전과 바뀐것이 없다면)

m에서 minus만큼 빼고 (전체 파티에서 거짓말을 못하는 파티의 수를 뺴고) 반복문에서 나온다.

아니라면 last를 minus로 바꾼다.

그후 반복문에서 나오면 m을 출력하면 된다.

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

using namespace std;

int n, m, k;
int uni[51];
bool know[51];
vector<int> party[51];

int find(int num) {
	if (uni[num] == num) return num;
	return find(uni[num]);
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) uni[i] = i, know[i] = false;
	cin >> k;
	int mi = -1;
	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		if (mi == -1) {
			mi = a;
		}
		uni[a] = mi;
		know[a] = true;
	}

	for (int i = 0; i < m; i++) {
		int a;
		cin >> a;
		for (int j = 0; j < a; j++) {
			int b;
			cin >> b;
			party[i].push_back(b);
		}
		sort(party[i].begin(), party[i].end());
	}

	int last = -1;
	while (1) {
		int minus = 0;
		for (int i = 0; i < m; i++) {
			bool chk = false;
			for (int j = 0; j < party[i].size(); j++) {
				if (know[find(party[i][j])]) {
					chk = true;
					break;
				}
			}
			if (chk) {
				minus++;
				know[find(uni[party[i][0]])] = true;
				for (int j = 0; j < party[i].size(); j++) uni[party[i][j]] = find(uni[party[i][0]]);
			}
		}
		if (last != -1 && last == minus) {
			m -= minus;
			break;
		}
		last = minus;
	}
	cout << m << endl;
}

전체코드다.