문제 개요

문제: 거짓말

분류: 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합

난이도: 골드4

문제 풀이

Union-Find 알고리즘을 사용한다.

1. 하나라도 같은 파티에 참여하는 인원들을 한 그룹으로 묶는다.
   • 각 파티마다 파티에 참여하는 첫 번째 사람과 나머지 사람들을 Union 한다.
2. 각 파티에 참여하는 첫 번째 사람과 진실을 아는 사람 중 한 명이라도 같은 그룹에 속한다면 정답을 1만큼 감소시킨다.
   • 첫 번째 사람과 진실을 아는 사람의 root가 같으면 서로 같은 그룹에 속한 것이며, 하나 이상의 같은 파티에 참가한다는 뜻이다.
   • 정답의 초기값은 파티의 수(M)이다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [NM, knowInfo, ...partyInfo] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const [N, M] = NM.split(" ").map(Number);
const [knowCnt, ...knowNum] = knowInfo.split(" ").map(Number);
partyInfo = partyInfo.map((info) => info.split(" ").slice(1).map(Number));

let root = Array.from({ length: N + 1 }, (_, i) => i);

const find = (x) => {
  if (x === root[x]) return x;
  return (root[x] = find(root[x]));
};

const union = (x, y) => {
  x = find(x);
  y = find(y);

  if (x != y) root[y] = x;
};

// 파티에 참가하는 첫 번째 사람과 나머지 사람들을 모두 union한다.
partyInfo.forEach((info, idx) => {
  info.forEach((i) => {
    union(partyInfo[idx][0], i);
  });
});

let answer = M;
for (let i = 0; i < M; i++) {
  for (let j = 0; j < knowCnt; j++) {
    // 파티에 참가하는 첫 번째 사람과 진실을 아는 사람의 root가 같다면
    // 하나 이상의 같은 파티에 참가한다는 뜻이므로 정답을 감소시킨다.
    if (find(partyInfo[i][0]) === find(knowNum[j])) {
      answer--;
      break;
    }
  }
}

console.log(answer);