[백준2617_자바스크립트(javascript)] - 구슬 찾기

🔴 문제

구슬 찾기

🟡 Sol

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

const lightGraph = Array.from({ length: n + 1 }, () => []);
const heavyGraph = Array.from({ length: n + 1 }, () => []);

for (const [a, b] of inputs) {
  lightGraph[a].push(b);
  heavyGraph[b].push(a);
}

const countReachable = (graph, start) => {
  const visited = Array(n + 1).fill(false);
  visited[start] = true;

  const queue = [start];
  let count = 0;

  while (queue.length > 0) {
    const node = queue.shift();
    count += 1;

    for (const neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }

  return count - 1; 
};

let lightCount = 0;
let heavyCount = 0;

for (let i = 1; i <= n; i++) {
  if (countReachable(lightGraph, i) > n / 2) lightCount++;
  if (countReachable(heavyGraph, i) > n / 2) heavyCount++;
}

console.log(lightCount + heavyCount);

🟢 풀이

⏰ 소요한 시간 : -

이 문제는 자기보다 무거운 구슬의 개수나 가벼운 구슬의 개수를 세어 전체 구슬의 절반보다 많으면 중간 무게가 될 수 없음을 판단하는 문제다.
그래서 나보다 무거운 구슬, 가벼운 구슬을 판단하기 위해 lightGraph, heavyGraph 두 개의 배열을 만들어 입력받은 두 구슬의 관계를 그래프에 추가해주었다.
그 후 lightGraph로 1번 구슬부터 n번 구슬까지 BFS를 수행해준다.
자기 자신과 연결된 모든 노드를 큐에 넣고, 하나의 노드를 제거할 때마다 count를 1 증가 해준다.
즉, 나보다 작은 구슬을 모두 큐에 넣고, 큐에 들어간 구슬보다 작은 구슬을 다시 큐에 넣는식인 그래프 탐색인 것이다.
모든 이웃 노드를 탐색한 후 자기자신을 제거한 count-1의 값을 리턴한다. 리턴한 값이 구슬의 개수 n의 절반보다 크다면 중간 무게가 될 수 없음을 판단하고 정답을 1 증가시켜주는문제다.
heavyGraph 도 동일한 과정을 거친 뒤 두 결과를 합해주면 정답이다.

🔵 Ref