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;
}