baekjoon 1043:거짓말

baekjoon 1043 거짓말

1043번 거짓말

접근

이 문제를 잘 이해하는 것이 중요하다.
이 문제는 사람들을 두 그룹으로 나누는 것이 핵심이다.
과장할 사람들과 진실을 말할 사람들로 나눠야한다.
즉, 한 사람에게는 진실 혹은 과장 하나만 말해야한다.
둘을 다 말하면 무조건 거짓이 들키는 조건이다.
과장을 먼저 말하고 진실을 말한다고 거짓이 들키지 않는게 아닌 것이다.
같은 파티에 참가한 사람들끼리 graph를 연결해둔다. 그런다음 처음부터 진실을 알고 있는 사람들을
시점으로 완전탐색(dfs)를 한다. 그 사람들은 진실 그룹이 된다.
그리고 그렇지 않은 사람들은 과장 그룹이 되어
이제 파티를 돌면서 과장 그룹 사람들만 있는 파티를 골라내면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void dfs(int i, vector<vector<bool>>& graph, vector<bool>& know);
int main(){
  int n, m;
  cin >> n >> m;
  int cntKnow; vector<int> firstKnow;
  vector<bool> know(n);
  cin >> cntKnow;
  while(cntKnow--){
    int a;
    cin >> a;
    firstKnow.push_back(a-1);
  }

  vector<vector<int>> party(m);
  vector<vector<bool>> graph(n, vector<bool>(n, false));
  for(int i = 0; i < m; i++){
    int a;
    cin >> a;
    while(a--){
      int b;
      cin >> b;
      party[i].push_back(b-1);
    }
  }
  //make graph
  for(auto i: party){
    if (i.size() > 1){
      for(int j = 0; j < i.size(); j++){
        for(int k = j+1; k < i.size(); k++){
          graph[i[j]][i[k]] = true;
          graph[i[k]][i[j]] = true;
        }
      }
    }
  }
  //firstKnow dfs
  for(auto i: firstKnow){
    know[i] = true;
    for(int j = 0; j < n; j++){
      if(graph[i][j]){
        dfs(j, graph, know);
      }
    }
  }
  //pick party
  int cnt = 0;
  for(auto i: party){
    bool flag = true;
    for(auto j: i){
      if(know[j]){
        flag = false;
        break;
      }
    }
    if(flag) cnt++;
  }
  cout << cnt << "\n";
  


  
  return 0;
}
void dfs(int i, vector<vector<bool>>& graph, vector<bool>& know){
  know[i] = true;
  for(int j = 0; j < graph[i].size(); j++){
    if(graph[i][j] && !know[j]){
      dfs(j, graph, know);
    }
  }
}

배운 점

골드부터는 좀 접근법이 바로 보이지는 않는 것 같다.