[백준][UnionFind] 1043 거짓말 NodeJs 구현

     

목차

 

 

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

문제

 

 

문제 구현 방향

오랜만에 문제를 풀다보니 유니온 파인드를 생각하지 못했다..

진실을 아는 사람이 섞이면 같은 그룹이 되기 때문에 유니온 파인드로 풀면 쉽게 해결할 수 있다.

 

 

문제 접근 방법

1. 먼저 각 그룹에 대해 유니온 파인드로 대표자를 만들어 준다.

2. 각 그룹에 대해서 대표자를 검사한 뒤 진실을 아는 사람의 대표자와 그 그룹의 대표자가 일치할 경우 카운트 해준다.

 

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let idx = 1;
let known;

let parent = Array(10000);
let rank = Array(10000).fill(0);

for (let i = 0; i < 10000; i++) {
  parent[i] = i;
}
function findParent(x) {
  if (x === parent[x]) return x;
  return (parent[x] = findParent(parent[x]));
}

function unionParent(x, y) {
  let a = findParent(x);
  let b = findParent(y);

  if (a === b) return;
  if (rank[a] < rank[b]) {
    parent[a] = b;
  } else if (rank[a] > rank[b]) {
    parent[b] = a;
  } else {
    parent[b] = a;
    rank[a] += 1;
  }
}

if (input[idx].length >= 1) {
  known = input[idx].trim().split(" ").map(Number);
  known.splice(0, 1);
}
idx++;
let present = [];
while (idx < input.length) {
  let a = input[idx].trim().split(" ").map(Number);
  a.splice(0, 1);
  for (let i = 0; i < a.length - 1; i++) {
    unionParent(a[i], a[i + 1]);
  }
  present.push(a[0]);
  idx++;
}


let ans = 0;

for (let i of present) {
    let flag = 0;
  for (let j of known) {
    if (findParent(i) === findParent(j)) {
        flag = 1;
        break;
    }
  }
  if(!flag)ans++;

}

console.log(ans);

 

 

 

+추가 NodeJs 메서드 활용 방법

--------------------------------------------

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [n, m] = input[0].trim().split(" ").map(Number);

let [truthCnt, ...truthKnowns] = input[1].trim().split(" ").map(Number);

let truthSet = new Set(truthKnowns);
let ans = 0;
const group = input
  .slice(2)
  .map((item) => item.slice(1).trim().split(" ").map(Number));

for (let i = 0; i < m; i++) {
  group.forEach((p) => {
    const truth = p.some((item) => truthSet.has(item));
    if (truth) {
      p.forEach((item) => truthSet.add(item));
    }
  });
}

group.forEach((p) => {
  const has = p.some((item) => truthSet.has(item));
  if (!has) ans++;
});



console.log(ans);