문제 개요

문제: 집합의 표현

분류: 자료 구조, 분리 집합

난이도: 골드5

문제 풀이

Union-Find 알고리즘으로 풀 수 있는 기본적인 문제였다.

합집합 연산 시 union 하고 같은 집합인지 확인하는 연산 시 find를 통해 루트의 동일 여부를 확인한다.

코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  solution(input);
  process.exit();
});

function solution(input) {
  const [n, m] = input.shift().split(" ").map(Number);
  const op = input.map((v) => v.split(" ").map(Number));
  const 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;
  };

  const answer = [];
  op.forEach(([func, a, b]) => {
    if (func === 0) union(a, b);
    else answer.push(find(a) === find(b) ? "YES" : "NO");
  });
  console.log(answer.join("\n"));
}

알게 된 점

readline 모듈로 입력 받기

코드를 제출했는데 런타임 에러(EACCES)가 떴다.

구글링 해보니 백준의 몇몇 문제에서는 node.js로 코드를 제출할 때 fs 모듈로 입력을 받으면 이 에러가 발생한다고 한다. fs 대신 readline 모듈로 입력을 받으면 해결되는듯 했다.

readline 모듈로 입력 받는 방법은 아래와 같다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  // line을 통해 입력 문자열이 들어옴
  input.push(line);
}).on("close", () => {
  // 입력이 끝난 후 수행할 로직 작성
  solution(input);
  process.exit();
});

그리고 몰랐던 사실인데 곧바로 로그를 찍어 그때그때 출력하는 것보다 출력할 것들을 모아 마지막에 한 번 출력하는 것이 훨씬 적은 시간이 드는 걸 발견했다.

readline 모듈에서만 그런 건지, fs 모듈에서도 그런 건지는 아직 모르겠지만 다음에 문제 풀 때 참고해야겠다.

// 아래 코드로 출력할 시 5868ms 소요
op.forEach(([func, a, b]) => {
	if (func === 0) union(a, b);
	else find(a) === find(b) ? console.log("YES") : console.log("NO");
});

// 아래 코드로 출력할 시 568ms 소요
const answer = [];
op.forEach(([func, a, b]) => {
	if (func === 0) union(a, b);
	else answer.push(find(a) === find(b) ? "YES" : "NO");
});
console.log(answer.join("\n"));

참고

🔗 [백준]node.js readline모듈로 입력받기