[백준] 나무 위의 빗물 #17073

후기

생각해보면 확률이 동일하기 때문에 leaf 노드에만 빗물이 쌓이게 된다.
따라서 확률은 (leaf 노드의 수) / W가 된다.
그래서 leaf 노드의 수를 dfs로 찾아준 후에 정답을 반환했다.

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, W] = input[0].split(' ').map(Number);
const nodes = input.slice(1).map((v) => v.split(' ').map(Number));

const solution = (N, W, nodes) => {
  const arr = Array.from(Array(N + 1), () => new Array());
  nodes.forEach(([n1, n2]) => {
    arr[n1].push(n2);
    arr[n2].push(n1);
  });
  let leafNodes = 0;
  const check = new Array(N + 1).fill(false);
  const dfs = (n) => {
    if (check[n]) return;
    check[n] = true;
    if (arr[n].length === 1 && check[arr[n][0]]) {
      leafNodes++;
      return;
    }
    for (const next of arr[n]) {
      dfs(next);
    }
  };
  dfs(1);
  return W / leafNodes;
};

console.log(solution(N, W, nodes));