[BOJ 1043] 거짓말

문제

거짓말

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

 

 

풀이

설명

과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 문제입니다.

 

어느 파티에 진실을 아는 사람이 한 명이라도 있으면, 지민이는 그 파티에서 진실만을 말해야 합니다.

 

Union-Find 알고리즘을 이용해 해결할 수 있습니다.

 

과정은 다음과 같습니다.

1. 같은 파티에 속해 있는 사람들을 같은 그룹으로 묶습니다.
2. 진실을 아는 사람들을 같은 그룹으로 묶습니다.
3. 어느 파티에 진실을 아는 사람과 같은 그룹에 묶여있는 사람이 있는지 확인하고, 없다면 카운트를 증가시킵니다.

 

예시 코드

function solution() {
  const [N, M] = input().split(" ").map(Number);
  const parent = Array.from({ length: N + 1 }, (_, idx) => idx);
  const truePeople = input().split(" ").map(Number).slice(1);
  const parties = Array.from({ length: M }, () =>
    input().split(" ").map(Number).slice(1)
  );
  let answer = 0;

  for (const party of parties) {
    for (let j = 1; j < party.length; j++) {
      union(party[0], party[j]);
    }
  }

  for (let i = 1; i < truePeople.length; i++) {
    union(truePeople[0], truePeople[i]);
  }

  for (const party of parties) {
    let canLie = true;

    for (const person of party) {
      if (find(person) === find(truePeople[0])) {
        canLie = false;
        break;
      }
    }

    if (canLie) answer++;
  }

  return answer;

  function union(x, y) {
    x = find(x);
    y = find(y);
    if (x !== y) parent[y] = x;
  }

  function find(x) {
    if (parent[x] === x) return x;
    return (parent[x] = find(parent[x]));
  }
}