[백준 2458] 키 순서 with node.js

📌 문제

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

📌 풀이

• 1번 정점에서 BFS(setComparabletallArr 함수) 를 시작하여 1번보다 큰 정점을 체크한다.
• 위의 방법으로 comparableTallArr라는 2차원 배열에 저장한다.
• comparableTallArr[1][i] = true 이면 는 1번 정점보다 키가 큰 i가 있다는 의미이고 comparableTallArr[i][1] = true 이면 1번 정점보다 키가 작은 i가 있다는 의미이다.
• comparableTallArr를 모두 돌면서 true인 값들의 cnt을 하면서

  cntOfcomparableTall = N - 1(본인 제외한 cnt)

를 구하면 된다.

📌 코드

const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString().trim()
    : `6 6
1 5
3 4
5 4
4 2
4 6
5 2`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

const setComparabletallArr = (comparableStudentNum) => {
  const visited = new Array(N + 1).fill(false);
  const queue = [comparableStudentNum];
  let queueCursor = 0;

  visited[comparableStudentNum] = true;

  while (queue.length > queueCursor) {
    const studentNum = queue[queueCursor++];

    for (let i = 1; i <= N; i++) {
      if (!visited[i] && comparableTallArr[studentNum][i]) {
        visited[i] = true;
        comparableTallArr[comparableStudentNum][i] = true;
        queue.push(i);
      }
    }
  }
};

const [N, M] = input().split(' ').map(Number);
const comparableTallArr = Array.from(Array(N + 1), () => new Array(N + 1).fill(false));
for (let i = 0; i < M; i++) {
  const [shortStudent, tallStudent] = input().split(' ').map(Number);
  comparableTallArr[shortStudent][tallStudent] = true;
}

for (let i = 1; i <= N; i++) {
  setComparabletallArr(i);
}

let totalCntOfcomparableTall = 0;
for (let studentNum = 1; studentNum <= N; studentNum++) {
  let cntOfcomparableTall = 0;
  for (let i = 1; i <= N; i++) {
    if (comparableTallArr[studentNum][i] || comparableTallArr[i][studentNum]) {
      cntOfcomparableTall += 1;
    }
  }

  if (cntOfcomparableTall == N - 1) {
    totalCntOfcomparableTall += 1;
  }
}

console.log(totalCntOfcomparableTall);