[백준] 1043-거짓말(C++)

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

1043번: 거짓말

 

구현문제입니다. 문제를 꼼꼼하게 읽는 습관을 길러야 할 것같습니다.

문제 조건중  어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 라는 조건에 주목해야합니다.

 

6 5

1 6

2 4 5

2 1 2

2 2 3

2 3 4

2 5 6

와 같은 테스트 케이스에서 답은 0 입니다. 

과장된 이야기를 먼저 들은 사람이 나중에 진짜 이야기를 들어도 거짓말쟁이인게 들통납니다. 

즉 순서가 상관이 없는 문제입니다. 

 

알고리즘 입니다. 

1. 만약 진실을 알고 있는 사람이 있다면 해당 파티에서 거짓말을 못합니다.

2. 진실을 알고있는 사람과 함께 파티에 참여한 사람들이 있다면, 해당 사람들이 진실을 알고있다고 표시합니다.

3.  2번 조건이 부합하면 다시 처음 파티부터 확인합니다. 

 

	#include <iostream>
	using namespace std;
	int n = 0, m = 0, result = 0;
	int num = 0, temp = 0;
	bool knowlege[51] = { 0 };
	bool val[50] = { 0 };
	int arr[50][51] = { 0 };
	int arr_index[50] = { 0 };
	int main() {
		cin >> n >> m; //사람의 수와 파티의 수
	
		cin >> num;
		for (int i = 0; i < num; i++) {
			cin >> temp;
			knowlege[temp] = 1;
		}

		for (int i = 0; i < m; i++) {
			cin >> num;
			arr_index[i] = num;
			for (int j = 0; j < num; j++)
				cin >> arr[i][j];
		}
	
		for (int i = 0; i < m; i++) {

			for (int j = 0; j < arr_index[i]; j++) {
				int v = arr[i][j];

				if (knowlege[v] == 1) {
					val[i] = 1; // 이파티에서 거짓말을 못해 
					bool jud2 = true;
					for (int k = 0; k < arr_index[i]; k++)
						if (knowlege[arr[i][k]] == 0 && j != k)
							jud2 = false, knowlege[arr[i][k]] = 1;

					if (jud2 == false) {
						i = -1;
						break;
					}

				}
			}

		}
	
		for (int i = 0; i < m; i++)
			if (val[i] == 0) result++; 


	
		cout << result << endl;
	}

구현 난이도 자체는 매우 낮은 문제지만 구현을 어떻게 할지 조금 생각해보아야 하는 문제였습니다.