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

1043번: 거짓말

그래프 탐색 문제.

그래프 탐색이라는 점을 발견한다면 어렵지 않게 풀 수 있다.

변수를 잘못 재사용해서 몇 번 틀려버려서 아쉬운 문제.

 

문제 풀이

문제는 다음과 같은 조건들이 있다.

• 지민이는 사실 혹은 과장(거짓말)을 말한다.
  
  
• 최초 사실을 아는 사람이 K명이라 할 때, 이 사람들에게는 사실만 말해야 한다.
  
  
• 사실을 들은 사람이 있다면 이 사람들이 있는 파티에서는 사실만 말해야 한다.
  즉, 사실 & 과장 둘 다 들을 수는 없다.

 

따라서 사실을 아는 사람이 있는 파티를 먼저 제거하고,

해당 파티에 있는 나머지 사람들도 사실을 들은 사람들이 되므로

나머지 사람들이 속한 다른 파티들도 거짓말을 할 수 있는 파티에서 제거한다.

 

결론적으로 사실을 들은 사람들을 계속해서 추가하면서 그 사람들이 속한 모든 파티를

제거해주면 된다.

 

문제 코드

 

/*
* 백준 1043번 거짓말
* https://www.acmicpc.net/problem/1043
* 그래프 탐색 / 분리 집합
*/
#include <iostream>
#include <vector>
using namespace std;

int peopleCnt, partyCnt;
int trueKnowPeopleCnt;
bool canLieParty[51];
bool trueAdd[51];
vector<int> trueKnowNumVec;
vector<vector<int>> partyPeopleNumVec(51, vector<int>());
vector<vector<int>> peopleJoinPartyVec(51, vector<int>());
int result;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> peopleCnt >> partyCnt;

	for (int i = 1; i <= partyCnt; i++) {
		canLieParty[i] = true;
	}

	cin >> trueKnowPeopleCnt;

	int trueKnowNum;
	while (trueKnowPeopleCnt--) {
		cin >> trueKnowNum;
		trueKnowNumVec.push_back(trueKnowNum);
		trueAdd[trueKnowNum] = true;
	}

	int partyJoinPeopleCnt, joinNum;
	for (int i = 1; i <= partyCnt; i++) {
		cin >> partyJoinPeopleCnt;
		for (int j = 1; j <= partyJoinPeopleCnt; j++) {
			cin >> joinNum;
			partyPeopleNumVec[i].push_back(joinNum);
			peopleJoinPartyVec[joinNum].push_back(i);
		}
	}

	for (int i = 0; i < trueKnowNumVec.size(); i++) {
		trueKnowNum = trueKnowNumVec[i];

		for (int j = 0; j < peopleJoinPartyVec[trueKnowNum].size(); j++) {
			int partyNum = peopleJoinPartyVec[trueKnowNum][j];

			canLieParty[partyNum] = false;

			int tmpCheck;
			for (int k = 0; k < partyPeopleNumVec[partyNum].size(); k++) {
				tmpCheck = partyPeopleNumVec[partyNum][k];

				if (!trueAdd[tmpCheck]) {
					trueKnowNumVec.push_back(tmpCheck);
					trueAdd[tmpCheck] = true;
				}

			}

		}
	}

	for (int i = 1; i <= partyCnt; i++) {
		if (canLieParty[i]) {
			result++;
		}
	}

	cout << result;

	return 0;
}

변수 설명

• peopleCnt, partyCnt : 사람의 수 N, 파티의 수 M
• trueKnowPeopleCnt : 진실을 최초로 아는 사람의 수
• canLieParty[51] : [i]번 파티에서 거짓말을 할 수 있는지 여부를 저장하는 배열
• trueAdd[51] : [i]번 사람이 진실을 알고 있는 벡터에 저장이 됐었는지 여부를 저장하는 배열
• trueKnowNumVec : 진실을 알고 있는 사람들의 번호를 담고있는 배열
• partyPeopleNumVec : 2차원 벡터. [i]번 파티에 참여한 사람들의 번호를 담고있는 벡터
• peopleJoinPartyVec : 2차원 벡터. [i]번 사람이 참여한 파티의 번호를 담고있는 벡터
• result : 출력할 결과값. (거짓말을 할 수 있는 파티의 수)

 

로직 설명

1. 모든 파티에서 거짓말을 할 수 있다고 가정하고 배열값을 초기화한다.
   
   
2. N, M 입력받은 후에 사실을 아는 사람의 수만큼 사람의 번호를 입력받고 
   사실을 아는 사람의 trueKnowNumVec 벡터에 입력해준다. 추후 중복 방지를 위해 해당 번호가
   이미 진실을 알고있다고 trueAdd 배열에 기록해둔다.
   
   
3. 후에 1번부터 partyCnt번 파티까지 참가하는 사람들의 수를 입력받고
   partyPeopleNumVec 벡터에 파티번호 - 참가하는 사람의 번호들 ,
   peopleJoinPartyVec 벡터에 참가하는 사람의 번호 - 파티 번호
   의 정보를 입력해둔다.
   
   
4. trueKnowNumVec 벡터를 돌아다니면서 사실을 아는 사람들의 파티를 제거해 나간다.
   canLieParty 배열에서 false로 바꿔준다.
   이 때 사실을 들은 사람들 중 trueAdd 배열에서 false값. 즉 추가되지 않은 경우에는
   해당 사람들도 trueKnowNumVec 벡터에 추가해준다.
   
   
5. canLieParty 배열을 돌아다니면서 true인 값의 개수를 출력해준다.

 

 

trueKnowNum이라는 변수를 재사용을 잘못해서 틀렸다.

 

백준 1043번 거짓말 · kimyunseok/cpp@9636c67