[JS] 백준 1717번 - 집합의 표현 - [런타임 에러 (EACCES)], 자료구조, 분리집합, 서로소집합 알고리즘, 그래프이론

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

1717번: 집합의 표현

 

 

📋풀이방법

✅서로소집합 알고리즘을 이용하면 간단하게 풀 수 있다.

https://ydoag2003.tistory.com/22

그래프이론(서로소집합)

 

1. parent라는 N+1 크기의 배열을 생성하고 각각 값을 해당되는 인덱스로 저장한다.

2. unionParent를 통해 a와 b의 값을 동일한 부모노드로 바꾼다.

3. findParent를 통해 a와 b의 부모노드가 같은지 확인하고 같으면 YES 아니면 NO로 출력한다.

 

 

🤟내 제출

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  solution(input);
  process.exit();
});
function solution(input) {
  function getParent(parent, x) {
    if (parent[x] == x) return x;
    return (parent[x] = getParent(parent, parent[x]));
  }
  function unionParent(parent, x, y) {
    let a = getParent(parent, x);
    let b = getParent(parent, y);
    if (a < b) parent[b] = a;
    else parent[a] = b;
  }
  function findParent(parent, x, y) {
    let a = getParent(parent, x);
    let b = getParent(parent, y);
    if (a == b) return true;
    else false;
  }
  const [N, M] = input.shift().split(" ").map(Number);
  const nodes = input.map((e) => e.split(" ").map(Number));
  let parent = Array.from({ length: N + 1 }, (_, idx) => idx);
  let result = [];
  for (let i = 0; i < M; i++) {
    let [H, a, b] = nodes[i];
    if (H == 1) {
      if (findParent(parent, a, b)) {
        result.push("YES");
      } else {
        result.push("NO");
      }
    } else {
      unionParent(parent, a, b);
      getParent(parent, a);
      getParent(parent, b);
    }
  }

  console.log(result.join("\n"));
}

 

 

 

💢어려웠던 점

1. 런타임 에러 (EACCES)

이 에러때문에 괜한 시간을 소비했다..

검색해보니 가끔 fs모듈로 인해 이런 에러가 생긴다고한다.

readline을 사용해서 위처럼 다시 코드를 재구성했다.

원래 코드는 아래와 같다.

 

fs모듈사용한 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");

function getParent(parent, x) {
  if (parent[x] == x) return x;
  return (parent[x] = getParent(parent, parent[x]));
}
function unionParent(parent, x, y) {
  let a = getParent(parent, x);
  let b = getParent(parent, y);
  if (a < b) parent[b] = a;
  else parent[a] = b;
}
function findParent(parent, x, y) {
  let a = getParent(parent, x);
  let b = getParent(parent, y);
  if (a == b) return true;
  else false;
}

let [N, M] = input.shift().split(" ").map(Number);
let parent = Array.from({ length: N + 1 }, (_, idx) => idx);
let arr = [];
let result = [];
for (let i = 0; i < M; i++) {
  let [H, a, b] = input.shift().split(" ").map(Number);
  if (H == 1) {
    if (findParent(parent, a, b)) {
      result.push("YES");
    } else {
      result.push("NO");
    }
  } else {
    unionParent(parent, a, b);
    getParent(parent, a);
    getParent(parent, b);
  }
}

console.log(result.join("\n"));

 

2. readline 사용법

- 일단 아래와 같이 처음을 규칙처럼 작성한다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  solution(input);
  process.exit();
});

-input.push(line);은 rl.close가 없어 입력을 무한히 받는 것인데 on(close)안에서 sloution함수를 통해 우리가 작성할 코드들을 넣어줘야한다

-나는 그냥 solution안에 안하고 그 안에다가만 하면 되지않나? 했는데 함수로 꺼내지 않으니까 왠지 모르게 작동이 안됐다..

-그래서 코드도 깔끔하게 바꿀겸해서 solution(input)으로 호출하고 아래에 함수를 작성한다.

function solution(input) { 
  
  ...
  
  const [N, M] = input.shift().split(" ").map(Number);
  const nodes = input.map((e) => e.split(" ").map(Number));
  
  
  ...
 }

-이런식으로 데이터를 받아오는 것인데 readlin도 잘 숙지해놓자.