BOJ 1043, 거짓말
ProblemSolving ·저는 이 문제를 BFS를 이용하여 풀었습니다.
풀이
모든 파티에서 같은 이야기를 한다고 생각하시면 이해가 편합니다.
처음부터 사실을 아는 사람도 있고 나중에 사실을 알게 되는 경우도 있습니다. 결국 거짓말을 칠 때 사실을 알게되거나 나중에라도 사실을 듣게되는 모든 경우를 제외해주어야 합니다. 그래서 생각한 것이 사람들을 노드로 생각하고 같은 파티끼리 간선으로 연결해줘서 탐색해주는 것입니다.
이렇게 탐색이 된 노드(사람들)이 있는 파티에서는 거짓말을 못치겠죠? 그럼 벡터에 입력값들을 받아놨다가 비교하여 답을 구해주면 됩니다.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
vector<vector<int>> v(51);
vector<vector<int>> input(51);
queue <int> q;
int n, m, s, cnt,chk[51];
void bfs()
{
while (!q.empty())
{
int now = q.front();
q.pop();
for (int i = 0; i < v[now].size(); i++)
{
int next = v[now][i];
if (chk[next] == 0)
{
chk[next] = 1;
q.push(next);
}
}
}
}
int main() {
scanf("%d %d", &n, &m);
scanf("%d", &s);
for (int i = 1; i <= s; i++)
{
int st;
scanf("%d", &st);
q.push(st);
chk[st] = 1;
}
for (int i = 1; i <= m; i++)
{
int a,b,c;
scanf("%d", &a);
scanf("%d", &b);
input[i].push_back(b);
for (int j = 2; j <= a; j++)
{
scanf("%d", &c);
v[b].push_back(c);
v[c].push_back(b);
input[i].push_back(c);
}
}
bfs();
cnt = m;
for(int i=1;i<=m;i++)
for (int j = 0; j < input[i].size(); j++)
if (chk[input[i][j]] == 1)
{
cnt--;
j = 51;
}
printf("%d", cnt);
return 0;
}