백준 1043, 거짓말

문제

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

풀이

사실 이 문제의 풀이가 직관적으로 떠오르지는 않았고 아 기존에 있던 사람에 의해서 다른 사람이 아는 사람으로 바뀌는구나 ~ 그럼 또 그 사람때문에 전염될 수 있구나~ 그럼 큐로 처리해야겠다 ~ 정도로 생각하고 진행했다. 그래서 시간복잡도도 계산하지 못하고 그냥 가장 효율적인 풀이로 구현하는데 집중했다.

해보고 나니까 O(n * m^2)가 나왔다. 하면서 간단한 수식 실수나 잘못된 변수를 넣은 곳이 많았는데 이런 실수를 줄이자.

실수

• 시간복잡도를 직관적으로 떠올리지 못함.
• 구현하는데 잔실수가 많았음.

코드

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<queue>

#define TRUE 1
#define FALSE 0

using namespace std;

int n, m;
vector<vector<int>> party_roster(51, vector<int>(0, 0)); // 해당 파티에 참가하는 사람
vector<vector<int>> attend_party(51, vector<int>(0, 0)); // 사람당 참가하는 파티
vector<int> known(51, 0); // 알고있는 사람
vector<int> known_party(51, 0); // 진실을 말해야 하는 파티
queue<int> que; // 새롭게 진실을 알게된 사람을 넣음

int main() {

	int people_num, temp;

	scanf("%d %d", &n, &m);

	scanf("%d", &people_num);

	for (int j = 0; j < people_num; j++) {

		scanf(" %d", &temp);

		known[temp] = TRUE;

	}

	for (int i = 1; i <= m; i++) {

		bool exist_known = FALSE;

		scanf(" %d", &people_num);

		for (int j = 0; j < people_num; j++) {

			scanf(" %d", &temp);

			party_roster[i].push_back(temp);
			attend_party[temp].push_back(i);

			if (known[temp] == TRUE) {

				known_party[i] = TRUE; 
				exist_known = TRUE;

			}

		}

		if(exist_known == TRUE){
			
			for (int j = 0; j < people_num; j++) {

				if (known[party_roster[i][j]] == FALSE) {

					que.push(party_roster[i][j]);
					known[party_roster[i][j]] = TRUE;

				}

			}
		
		}

	}

	while (!que.empty()) {

		int temp = que.front();
		que.pop();

		for (int i = 0; i < attend_party[temp].size(); i++) { // 진실을 알게된 사람이 참여한 파티를 확인

			int party = attend_party[temp][i];

			if (known_party[party] == FALSE) { // 거짓말을 하면 안됨

				for (int j = 0; j < party_roster[party].size(); j++) { // 새롭게 진실을 알게된 사람을 큐에 추가

					if (known[party_roster[party][j]] == FALSE) {

						que.push(party_roster[party][j]);
						known[party_roster[party][j]] = TRUE;

					}

				}

				known_party[party] = TRUE;

			}

		}

	}

	int result = 0;

	for (int i = 1; i <= m; i++) {

		if (known_party[i] == FALSE)
			result++;

	}

	printf("%d", result);

	return 0;

}