1043 ๊ฑฐ์ง“๋ง

์•Œ๊ณ ๋ฆฌ์ฆ˜(DFS)

1. ์ฒ˜์Œ ์ง„์‹ค์„ ์•Œ๊ณ ์žˆ๋Š” ์‚ฌ๋žŒ๊ณผ ์—ฐ๊ฒฐ๋ผ์žˆ๋Š” ํŒŒํ‹ฐ ๊ทธ๋ฃน๊ณผ, ์ ˆ๋Œ€ ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์€ ๊ทธ๋ฃน์„ ๋‚˜๋ˆ ์•ผํ•จ.

2. ๋‚˜๋Š” ๋‹จ์ˆœํžˆ ๋ณ€ํ™”๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜์˜€์Œ. ๊ทธ๋ฆฌ๊ณ  ๊ทธ๋Ÿฐ ์‚ฌ๋žŒ์ด ์—†๋Š” ๊ทธ๋ฃน์˜ ๊ฐœ์ˆ˜๋งŒ ์„ธ์„œ ์ถœ๋ ฅํ•จ.

๋‹ค๋ฅธ ํ’€์ด

1. ๋‚ด๊บผ์—์„œ ์ข€๋” ์ตœ์ ํ™”๋œ ํ’€์ด
2. ์ฒ˜์Œ์— ์ž…๋ ฅ์„ ๋ฐ›์œผ๋ฉด์„œ, ๊ฐ ์‚ฌ๋žŒ๋“ค์ด ์–ด๋”” ํŒŒํ‹ฐ์™€ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋Š”์ง€ ๋ฒกํ„ฐ์— ์ €์žฅ.
3. ์ฒ˜์Œ๋ถ€ํ„ฐ ์ง„์‹ค์„ ์•Œ๊ณ  ์žˆ๋Š” ์‚ฌ๋žŒ๋“ค์ด ์žˆ๋Š” ๊ทธ๋ฃน์„ ํ์— ๋„ฃ๊ณ , ๊ฑฐ์ง“๋ง์„ ํ•  ์ˆ˜ ์žˆ๋Š” ๊ทธ๋ฃน์ธ์ง€ ์ฒดํฌํ•˜๋Š” ๋ฐฐ์—ด์— ํ‘œ์‹œ
4. ํ์— ๋„ฃ์–ด์ง„ ๊ทธ๋ฃน๋“ค์„ ํ•˜๋‚˜์”ฉ ๋นผ๊ฐ€๋ฉฐ, ๊ทธ ๊ทธ๋ฃน์— ์žˆ๋Š” ์‚ฌ๋žŒ๋“ค์ด ์†ํ•œ ๊ทธ๋ฃน๋„ ํ์— ์ถ”๊ฐ€.
	์ด๋ฏธ ๊ฒ€์‚ฌํ•œ ์‚ฌ๋žŒ์ด๊ฑฐ๋‚˜, ๊ฒ€์‚ฌํ•œ ๊ทธ๋ฃน์ด๋ฉด ํŒจ์Šค
5. ๊ทธ๋ ‡๊ฒŒํ•ด์„œ ํƒ์ƒ‰์ด ๋๋‚˜๋ฉด, ํ‘œ์‹œ์•ˆ๋œ ๊ทธ๋ฃน์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ์„œ ์ถœ๋ ฅ

์ฝ”๋“œ

#include <iostream>
 
using namespace std;
 
int N, M, party[51][51];
bool knowTruth[51], alreadyCheck[51];
 
int getAns();
void makeKnow();
 
int main() {
	cin >> N >> M;
	int t;
	cin >> t;
	while(t--) {
		int a;
		cin >> a;
		knowTruth[a] = true;
	}
 
	for (int i = 0; i < M; i++) {
		int n;
		cin >> n;
		for (int j = 0; j < n; j++)
			cin >> party[i][j];
	}
	makeKnow();
	cout << getAns();
}
 
void makeKnow() {
	bool change = true;
	while (change) {
		change = false;
 
		for (int i = 0; i < M; i++) {
			if (alreadyCheck[i])
				continue;
 
			int index = 0;
			bool check = false;
			while (party[i][index] != 0) {
				if (knowTruth[party[i][index]]) {
					check = true;
					break;
				}
				index++;
			}
 
			if (check) {
				change = true;
				alreadyCheck[i] = true;
				index = 0;
				while (party[i][index] != 0) {
					knowTruth[party[i][index]] = true;
					index++;
				}
			}
		}
	}
}
 
int getAns() {
	int result = 0;
	for (int i = 0; i < M; i++) {
		int index = 0;
		bool check = true;
		while (party[i][index] != 0) {
			if (knowTruth[party[i][index]]) {
				check = false;
				break;
			}
			index++;
		}
		if (check)
			result++;
	}
	return result;
}