[BOJ] 1043 - 거짓말

https://www.acmicpc.net/problem/1043

BOJ - 거짓말

문제 유형: 유니온-파인드, BFS, DFS, 그래프
문제 난이도: Gold IV
시간 제한: 2초
메모리 제한: 128MB
 

문제

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
 

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.
 

출력

첫째 줄에 문제의 정답을 출력한다.
 

풀이

유니온-파인드를 이용해서 풀 수 있다.
핵심은 컴포넌트의 연결이다. 진실을 아는 사람 또는 진실을 아는 사람과 연관된 사람이 한 명도 없는 그룹이어야 그 그룹에 거짓말을 할 수 있다.
 
우선, 참여자 리스트 participants[i]에는 i번째 사람이 진실을 알고 있는지에 대한 여부를 저장한다.
party[i]에는 파티의 구성원들을 저장해놓는다.
파티 구성원을 입력받으면서, 구성원들 간의 union관계를 맺는다.
 
파티 구성원들을 다시 살펴보면서, 진실을 아는 구성원의 그룹의 루트를 구해서, 그 루트가 진실을 알고 있음을 마킹해놓는다.
다시 모든 파티의 구성원을 보면서, 파티 구성원의 루트를 구해서, 그 루트가 진실을 모른다면 된다.
모든 구성원이 몰라야만 그 그룹에 거짓말을 할 수 있다.
 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, m;

int getRoot(vector<int> &parent, int x) {
  if (parent[x] == -1)
    return x;
  return parent[x] = getRoot(parent, parent[x]);
}

void unionElement(vector<int> &parent, int x, int y) {
  int xRoot = getRoot(parent, x);
  int yRoot = getRoot(parent, y);
  if (xRoot != yRoot) {
    if (xRoot < yRoot)
      parent[yRoot] = xRoot;
    else
      parent[xRoot] = yRoot;
  }
}

int main() {
  cin >> n >> m;

  int k;
  cin >> k;
  vector<bool> participants(n + 1, false); // true: knows the truth
  for (int i = 0; i < k; ++i) {
    int temp;
    cin >> temp;
    participants[temp] = true;
  }

  vector<int> parent(n + 1, -1);
  vector<vector<int>> parties(m);

  for (int i = 0; i < m; ++i) {
    cin >> k;
    for (int j = 0; j < k; ++j) {
      int participant;
      cin >> participant;
      parties[i].push_back(participant);
      if (j > 0) {
        unionElement(parent, parties[i][j], parties[i][j - 1]);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (participants[i]) {
      participants[getRoot(parent, i)] = true;
    }
  }

  int ans = 0;
  for (int i = 0; i < m; ++i) {
    bool canLie = true;
    for (const auto &member : parties[i]) {
      if (participants[getRoot(parent, member)]) {
        canLie = false;
        break;
      }
    }
    if (canLie)
      ans++;
  }

  cout << ans << "\n";

  return 0;
}