[백준 1043번 C/C++] 거짓말

 

[백준 1043번 C/C++] 거짓말

 

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

1043번: 거짓말

---

 

해결전략

 

Set

 

---

 

처음 시도한 코드 - 테스트 케이스 모두 통과

 

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

int n, m; // n: 사람의 수, m: 파티의 수
int k; // k: 진실을 아는 사람의 수
set<int> truth; // 진실을 아는 사람들을 담는 배열
int nVisiters; // nVisiters: 파티에 오는 사람의 수
vector<vector<int>> v;

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

	cin >> n >> m;
	cin >> k;
	int input;
	for (int i = 0; i < k; i++) {
		cin >> input;
		truth.insert(input);
	}

	v.resize(m);

	for (int t = 0; t < m; t++) // 파티 수 만큼 시행
	{
		bool knowTruth = false;

		cin >> nVisiters;
		vector<int> visiter(nVisiters); // 파티에 오는 사람들을 담는 배열
		for (int i = 0; i < nVisiters; i++) {
			cin >> visiter[i];
			v[t].push_back(visiter[i]);

			// 진실을 아는 사람들이 파티원 중에 있는지 검사
			if (truth.find(visiter[i]) != truth.end()) {
				knowTruth = true; // 파티원 중 한 명이라도 진실을 말하는 사람이 있다면 true
			}
		}

		if (knowTruth) { // 진실을 아는 사람들과 같은 파티에 참석한 사람들 모두를 truth에 추가
			for (int i = 0; i < nVisiters; i++)
				truth.insert(visiter[i]);
		}
	}

	int answer = m;
	for (int t = 0; t < m; t++) // 파티 수 만큼 시행
	{
		for(int i = 0; i < v[t].size(); i++)
		{
			if(truth.find(v[t][i]) != truth.end())
			{
				answer--; // 전체 파티수에서 진실만을 얘기해야 되는 파티 수를 뺌
				break;
			}
		}
	}

	cout << answer << "\n";

	return 0;
}

 

---

 

정답 코드

 

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

int n, m; // n: 사람의 수, m: 파티의 수
int k; // k: 진실을 아는 사람의 수
set<int> truth; // 진실을 아는 사람들을 담는 배열
int nVisiters; // nVisiters: 파티에 오는 사람의 수
vector<vector<int>> v;

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

	cin >> n >> m;
	cin >> k;
	int input;
	for (int i = 0; i < k; i++) {
		cin >> input;
		truth.insert(input);
	}

	v.resize(m); // 파티의 수만큼 2차원 벡터의 크기를 조절

	for (int t = 0; t < m; t++) // 파티 수 만큼 시행
	{
		cin >> nVisiters;
		vector<int> visiter(nVisiters); // 파티에 오는 사람들을 담는 배열
		for (int i = 0; i < nVisiters; i++) {
			cin >> visiter[i];
			v[t].push_back(visiter[i]); // 2차원 벡터에 참석자 정보를 추가
		}
	}

	while (true) // 진실을 아는 사람이 더 이상 추가되지 않을 때까지 반복
	{
		bool updated = false;

		for (int t = 0; t < m; t++) 
		{
			bool knowTruth = false;

			for (int i = 0; i < v[t].size(); i++) 
			{
				if (truth.find(v[t][i]) != truth.end()) { // 해당 참석자가 진실을 아는 경우
					knowTruth = true; // 해당 파티에는 진실을 아는 참석자가 있다는 표시를 함
					break;
				}
			}

			if (knowTruth) // 해당 파티에 진실을 아는 참석자가 있는 경우
			{
				for (int i = 0; i < v[t].size(); i++) {
					if (truth.insert(v[t][i]).second) {// 참석자를 진실을 아는 사람의 집합에 추가. 이미 있는 경우 추가되지 않음
						updated = true; // 새로운 사람이 진실을 알게 됨을 표시
					}
				}
			}
		}

		if (false == updated) { // 더 이상 새로운 사람이 진실을 알게 되지 않은 경우 반복 종료
			break;
		}
	}
	

	int answer = m;
	for (int t = 0; t < m; t++) // 파티 수 만큼 시행
	{
		for(int i = 0; i < v[t].size(); i++)
		{
			if(truth.find(v[t][i]) != truth.end())
			{
				answer--; // 전체 파티수에서 진실만을 얘기해야 되는 파티 수를 뺌
				break;
			}
		}
	}

	cout << answer << "\n";

	return 0;
}

 

 

---