백준4803 - 트리 (find-union) node.js

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

문제는 각각의 테스트케이스가 존재할 때, 해당 테스트에 대해 트리를 헤아린 뒤 그 갯수에 따라 텍스트를 반환하는 문제다. 다만, 사이클이 존재하는 경우 그 경우는 헤아리지 않고 반환함을 주의해야 한다.

 

문제 풀이 방식

근래 들어 가장 오래 붙잡고 있던 문제였다. 사이클과 트리에서 힌트를 얻어, Find-Union 알고리즘으로 접근하고 사이클을 이루는 정점은 따로 빼주며 진행하는 데까지는 어렵지 않았으나, 마지막 사이클에 포함되지 않은 정점과 사이클에 포함된 정점을 계산하는 과정에서 많이 헤맸다.

 

전체 소스 코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "입력.txt")
  .toString()
  .trim()
  .split("\n");

function solution(data) {
  const arr = data.map((el) => el.split(" ").map(Number));
  const testCase = [];
  // 테스트 케이스 나누기
  for (let i = 0; i < arr.length; i++) {
    const [n, m] = arr[i];
    if (n == 0 && m == 0) break;
    testCase.push(arr.slice(i, i + m + 1));
    i += m;
  }

  const result = testCase.map((el, idx) => act(idx, el));
  console.log(result.join("\n"));
}

// find-union 을 실행하는 함수
function act(idx, edges) {
  const [n, _] = edges.shift(); // 정점 수 n
  const roots = {}; // 루트 정점을 담을 객체
  for (let i = 1; i <= n; i++) roots[i] = i;

  function find(node) {
    if (node !== roots[node]) roots[node] = find(roots[node]);
    return roots[node];
  }

  const cycleSet = new Set(); // 사이클을 이루는 정점을 담을 set
  function union(a, b) {
    const x = find(a),
      y = find(b);

    if (x === y) cycleSet.add(x); // 두 정점의 루트가 같다면 사이클
    else if (x < y) roots[y] = x;
    else roots[x] = y;
  }

  edges.forEach(([s, e]) => {
    union(s, e);
  });
  
  // 모든 union이 끝난 뒤 루트 재정립 (이 과정을 생각못해 헤맸다)
  const rootsSet = new Set();
  for (let i = 1; i <= n; i++) {
    const root = find(i);
    rootsSet.add(root);
  }
  
  // cycleSet에 담긴 요소 또한 루트 재정립한 뒤 cycleRootsSet에 추가
  const cycleRootsSet = new Set();
  const temp = [...cycleSet];
  temp.forEach((root) => {
    cycleRootsSet.add(find(root));
  });
  
  // 사이클 혹은 트리를 이루는 rootsSet - 사이클을 이루는 cycleRootsSet의 크기를 뺌
  const result = rootsSet.size - cycleRootsSet.size;

  const txt = `Case ${idx + 1}: `;
  return (
    txt +
    (0 >= result
      ? "No trees."
      : result == 1
      ? "There is one tree."
      : `A forest of ${result} trees.`)
  );
}

solution(input);