[C++ 백준 문제풀이] 백준 1043번: 거짓말

 

문제 요약 :

 

지민이는 엄청난 거짓말쟁이.

모든 파티에 참석하는데, 거짓말을 한다는 사실을 들통나지 않으면서 최대한 거짓말을 많이 해야함.

진실을 아는 사람이 포함된 파티에서는 진실만 말하게 됨.

진실을 아는사람과 완전히 분리된 파티에서만 진실을 말할  수 있음.

 

 

 

풀이 전략 :

 

> 진실을 아는 사람과 같은 파티에 참여한 사람도 진실을 아는 사람이 됨

> 진실을 아는 사람들을 bool형으로 정의하여 새로 추가함, 추가 할 때마다 다시 반복문을 처음으로

> 처음으로 되돌릴 때 추가 연산을 방지하기 위해 추가한 라인을 다시 검사 안하도록 조건 추가

 

변수목록

> vector을 활용(공간을 딱 맞추는것을 좋아하는 개인선호)

> 파티의 참가자 ( 2차원배열 활용 party)

> 진실을 아는 사람의 집합( bool형 trueNum)

> 거짓말을 한 파티의 여부( bool형 resulatNum) ( 추가연산 방지 )

 

 

코드

#include <iostream>
#include <vector>
int main() {
	int n, m;
	std::cin >> n >> m;

	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	std::vector<std::vector<int>> party(m, std::vector<int>(0));
	std::vector<bool> trueNum(n + 1, true);
	std::vector<bool> resultNum(m, true);

	int t;
	std::cin >> t;

	for (int i{ 0 }; i < t; i++) {
		int temp;
		std::cin >> temp;
		trueNum[temp] = false;
	}

	for (int i{ 0 }; i < m; i++) {
		int num;
		std::cin >> num;

		for (int j{ 0 }; j < num; j++) {
			int temp;
			std::cin >> temp;
			party[i].push_back(temp);
		}
	}

	for (int i{ 0 }; i < m; i++) {
		for (int j{ 0 }; j < party[i].size(); j++) {

		}
	}

	for (int i{ 0 }; i < m; i++) {
		if (!resultNum[i]) continue;
		for (int j{ 0 }; j < party[i].size(); j++) {
			if (!trueNum[party[i][j]]) {
				for (int a{ 0 }; a < party[i].size(); a++) {
					trueNum[party[i][a]] = false;
				}
				j = party[i].size();
				resultNum[i] = false;
				i = -1;
				break;
			}
		}
	}

	int total = 0;
	for (int i{ 0 }; i < m; i++) {
		if (resultNum[i]) total++;
	}

	std::cout << total << "\n";
}

 

 

문제를 풀고보니 유니온 파인드 알고리즘을 활용해야 했었음....

n,m이 50 이하라 큰 차이가 안나는것으로 판단!