백준 1043 - 거짓말

문제 링크입니다 https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

지민이의 이야기의 진실을 알고 있는 사람들을 피해서 거짓말을 말할 수 있는 파티의 최대 갯수를 찾는 문제입니다.

 

진실을 알고 있는 사람이 있는 파티는 거짓말을 하면 들통이 남으로 무조건 진실을 말해야하며 진실을 모르는 사람만 있는 파티인 경우에는 사람들이 진위 여부를 가릴 수 없어 지민이는 거짓말을 합니다.

 

진실을 알고 있는 사람들을 - A, B, C, D, E .....

진실을 모르는 사람들을 - 1, 2, 3, 4....              라고 하겠습니다.

 

1번 파티에 1,A가 참여하고 2번 파티에 1,2가 참여를 한다고 가정한다면 지민이는 2개 파티 모두 거짓말을 못합니다.

왜냐하면 첫번째 파티에서 1이 진실을 들었기에 두번째 파티에서 지민이가 거짓말을 한다면 거짓임을 알 수 있기 때문입니다. -> 이것을 염두하고 문제를 접근해야 합니다.

 

저는 각 파티에 참석하는 사람들의 번호 모임 / 각 번호의 사람이 참석하는 파티들의 모임 이 2개를 저장하는 백터를 만들었습니다. 또한 거짓말을 아는 사람들을 저장하기 위해서 큐를 하나 만들었습니다.

 

입력을 받은 후에 만약 진실을 아는 사람이 없다면 모든 파티에서 거짓말을 해도 됨으로 파티의 수를 출력하고 끝냅니다. 하지만 진실을 아는 사람이 있다면 tell_lie() 함수를 실행했습니다.

 

tell_lie() 함수는 큐에 저장했던 진실을 아는 사람들을 이용합니다. 큐가 빌때까지 반복을 하는데 진실을 아는 사람이 참석하는 파티를 찾습니다. 그렇다면 그 파티에서는 무조건 진실을 말할 수 밖에 없는데, 이때 같이 동석하는 사람들의 번호를 찾은 뒤 모두 진실을 알고 있다고 해줍니다(저는 truth 배열을 만들어 판별했습니다). 이 사람들을 전부 큐에 넣어줍니다.

 

이 방법을 끝까지 해준 뒤에 party 백터에 저장된 사람들이 모두 진실을 모른다면 거짓말을 할 수 있는 파티의 갯수를 하나 증가합니다. 마지막에 파티의 갯수를 출력하면 됩니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int number_people, number_party;
int number_know;
int cnt;
queue<int> know_secret; // 비밀을 아는 사람들의 번호
vector<int> party[51];  // 각 파티에 참석하는 사람들의 번호를 저장
vector<int> people[51]; // 각 번호의 사람이 가는 파티를 저장
bool truth[51];

void find(int x);

void tell_lie() {
	while(!know_secret.empty()) {
		int p = know_secret.front();
		know_secret.pop();
		for (int i = 0; i < people[p].size(); i++) {
			find(people[p][i]);
		}
	}
}

void find(int x) {
	for (int i = 0; i < party[x].size(); i++) {
		if (truth[party[x][i]] == false) {
			truth[party[x][i]] = true;
			know_secret.push(party[x][i]);
		}
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> number_people >> number_party;
	cin >> number_know;
	for (int i = 0; i < number_know; i++) {
		int a;
		cin >> a;
		truth[a] = true;
		know_secret.push(a);
	}
	for (int i = 1; i <= number_party; i++) {
		int peoples;
		cin >> peoples;
		for (int j = 0; j < peoples; j++) {
			int a;
			cin >> a;
			party[i].push_back(a);
			people[a].push_back(i);
		}
	}

	/*for (int i = 1; i <= number_people; i++) {
		cout << i << " ";
		for (int j = 0; j < people[i].size(); j++) {
			cout << people[i][j] << " ";
		}
		cout << "\n";
	}*/

	if (number_know == 0) {
		cout << number_party;
		return 0;
	}
	else {
		tell_lie();
	}

	for (int i = 1; i <= number_party; i++) {
		int know_truth = 0;
		for (int j = 0; j < party[i].size(); j++) {
			if (truth[party[i][j]] == true) {
				know_truth++;
			}
		}
		if (know_truth == 0) {
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

 

질문 및 조언 댓글 남겨주세요