[백준4803_자바스크립트(javascript)] - 트리

🔴 문제

트리

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

let front = 0;
let testcase = 1;
while (front < inputs.length - 1) {
  const [n, m] = inputs[front++];
  const p = Array.from({ length: n + 1 }, (_, idx) => idx);
  const cycles = [];
  let ans = 0;

  const find = (a) => {
    if (a !== p[a]) p[a] = find(p[a]);

    return p[a];
  };

  const union = (a, b) => {
    const pa = find(a);
    const pb = find(b);

    p[pb] = pa;
  };

  for (let _ = 0; _ < m; _++) {
    const [s, e] = inputs[front++];
    const ps = find(s);
    const pe = find(e);

    if (ps === pe) cycles.push(s);
    else union(s, e);
  }

  for (let i = 1; i <= n; i++) {
    find(i);
  }

  const set = new Set();
  for (const cycle of cycles) {
    set.add(p[cycle]);
  }

  for (let i = 1; i <= n; i++) {
    if (set.has(p[i])) continue;
    ans += 1;
    set.add(p[i]);
  }

  if (ans > 1) console.log(`Case ${testcase++}: A forest of ${ans} trees.`);
  else if (ans === 1) console.log(`Case ${testcase++}: There is one tree.`);
  else console.log(`Case ${testcase++}: No trees.`);
}

🟢 풀이

⏰ 소요한 시간 : -

union-find를 통해 트리를 찾는 문제다.

while+front변수로 여러개의 테스트 케이스를 처리해줬다.
테스트 케이스마다 n, m을 입력받고 부모노드를 저장할 배열 p와 사이클 형성 여부를 저장할 배열 cycles, 정답을 셀 변수 ans, union, find 함수를 각각 정의한다.

그 후 정점간의 연결정보 s와 e를 입력받는다.
두 정점은 연결되어 있으므로 find연산을 통해서 각 정점이 같은 부모를 가르키는지 확인한다.
만약 같은 부모를 가르키고 있다면 사이클을 형성한다는 의미이므로 cycles 배열에 s를 넣어준다. (e를 넣어줘도 됨. 어차피 같은 사이클이므로)
만약 같은 부모를 가르키고 있지 않다면 두 정점을 union연산해 이어준다.

m개의 정점 연결 처리를 다 해주면 모든 정점들에 find연산을 수행해 각 정점들의 대표부모를 가르킬 수 있도록 한다.

그 후 아까 찾은 사이클 배열들의 대표부모를 찾아야 한다. 그래서 사이틀의 부모를 찾아 이를 set이라는 집합에 넣어주고, 마지막으로 set에 포함되지 않은 정점의 개수만 세어주면된다.
이 때 한번 세어준 정점은 중복되지 않도록 세고난 뒤 set에 포함한다.

🔵 Ref