본문 바로가기
알고리즘 문제풀이/백준

[백준 1043] 거짓말

by m2162003 2021. 1. 30.

www.acmicpc.net/problem/1043

 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

 

union-find 써야하는데...까지만 파악한 문제

 

유니온 파인드쓰는 것 까지는 쉽게 캐치가 가능하나 그걸로 끝이 아니었다.

1. 같은 파티에 있는 사람을 체크

2. 파티로 연결된 사람들 체크

3. 진실을 말하면 안되는 사람들이 있는 파티 체크

이렇게 3가지가 필요한데 3가지가 동시에 진행되기는 힘들다.

 

따라서 1,2는 유니온 파인드를 사용하여 사람들을 연결하고

3은 파티별로 돌면서 참가자 중 진실을 말하면 안되는 사람을 체크한다.

#include <stdio.h>
#include <vector>

using namespace std;
int n, m;
int t;
vector<int> truth;
vector<int> v[51];
int parent[51];

int find_parent(int p1)
{
  if (parent[p1] == p1)
  {
    return p1;
  }

  return parent[p1] = find_parent(parent[p1]);
}

void union_parent(int p1, int p2)
{

  int pp1 = find_parent(p1);
  int pp2 = find_parent(p2);

  if (pp1 < pp2)
  {
    parent[pp2] = pp1;
  }
  else
  {
    parent[pp1] = pp2;
  }
}
int main(void)
{
  scanf("%d%d", &n, &m);
  scanf("%d", &t);
  for (int i = 0; i < t; i++)
  {
    int tmp;
    scanf("%d", &tmp);
    truth.push_back(tmp);
  }

  for (int i = 1; i <= n; i++)
  {
    parent[i] = i;
  }

  for (int i = 0; i < m; i++)
  {
    int num;
    scanf("%d", &num);
    for (int j = 0; j < num; j++)
    {
      int tmp;
      scanf("%d", &tmp);
      v[i].push_back(tmp);
    }
  }

  for (int i = 0; i < m; i++)
  {
    int fir = v[i][0];
    for (int j = 1; j < v[i].size(); j++)
    {
      int next = v[i][j];
      union_parent(fir, next);
    }
  }
  int res = m;
  for (int i = 0; i < m; i++)
  {
    bool party = true;
    for (int j = 0; j < v[i].size(); j++)
    {

      if (!party)
        break;

      int cur = v[i][j];

      for (int k = 0; k < truth.size(); k++)
      {
        if (find_parent(cur) == find_parent(truth[k]))
        {
          party = false;
          break;
        }
      }
    }

    if (!party)
      res--;
  }

  printf("%d\n", res);
  return 0;
}

댓글