백준 17073 < 나무 위의 빗물 > JavaScript

📍문제 링크

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

17073번: 나무 위의 빗물

 

📍알고리즘 분류

- 수학

- 그래프 이론

- 그래프 탐색

- 트리

 

📍문제 풀이

간선 정보를 바탕으로 트리를 만들고, 루트에 물을 흘려보낸다

 

한 턴에 발생하는 동작은 아래와 같다

- 부모 노드가 1 이상의 물을 갖고 있다면 랜덤한 자식 노드에 1의 물을 흘려보냄

- 자식 노드는 물을 받고 저장

 

더 이상 물이 움직이지 않는 상태에 도달하면

(즉, 물이 모든 리프에 있다면)

물을 가진 각 정점이 가진 물의 양의 평균을 구하라

 

⭐문제를 어렵게 생각할 필요 없다. 완성된 형태를 생각해보면...

완성된 형태

leaf node 에만 물이 존재할 것이고, 각 leaf node의 물의 양 total은 처음에 넣은 물의 양 W 이다.

따라서 W / leaf node의 수 를 구하면 된다

 

즉, leaf node의 갯수를 구하는 아주 쉬운 문제이다

- 트리를 순회할 필요도 없이 인접 리스트만 구할 수 있으면 풀 수 있는 문제이다

 

📍코드 (JavaScript)

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

const input = [];

class Tree {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(num) {
    if (!this.adjacencyList[num]) this.adjacencyList[num] = [];
  }
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  bfs(start) {
    let percent = 1;
    const queue = [start];
    const obj = {};
    const isVisited = { [start]: true };
    while (queue.length) {
      const currentVertex = queue.shift(); // 1
      let childNodesNum = this.adjacencyList[currentVertex].length;
      if (childNodesNum === 1) continue;
      if (currentVertex !== 1)
        childNodesNum = this.adjacencyList[currentVertex].length - 1;
      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!isVisited[neighbor]) {
          isVisited[neighbor] = true;
          if (obj[neighbor]) obj[neighbor] += percent / childNodesNum;
          else obj[neighbor] = percent / childNodesNum;
          queue.push(neighbor);
        }
      });
      percent /= childNodesNum;
    }
    return obj;
  }
}

const tree = new Tree();

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [N, W] = input.shift().split(" ").map(Number);
  for (let i = 1; i <= N; i++) {
    tree.addVertex(i);
  }
  for (let el of input) {
    const [v1, v2] = el.split(" ").map(Number);
    tree.addEdge(v1, v2);
  }
  let leafNum = 0;
  for (let vertex in tree.adjacencyList) {
    if (vertex !== "1" && tree.adjacencyList[vertex].length === 1) {
      leafNum++;
    }
  }
  console.log(W / leafNum);
});

 

📍리뷰

- 사실 처음에는 어렵게 생각해서 BFS를 통해 각 부모노드가 가진 자식 노드의 수를 바탕으로 확률을 계산하며 각 정점별로 더해나갔다

- 그래도 답은 예제와 같게 출력되나 시간이 오래 걸려서 오답으로 나왔다

- 닭 잡는 칼 대신 소 잡는 칼

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

const input = [];

class Tree {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(num) {
    if (!this.adjacencyList[num]) this.adjacencyList[num] = [];
  }
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  bfs(start) {
    let percent = 1;
    const queue = [start];
    const obj = {};
    const isVisited = { [start]: true };
    while (queue.length) {
      const currentVertex = queue.shift(); // 1
      let childNodesNum = this.adjacencyList[currentVertex].length;
      if (childNodesNum === 1) continue;
      if (currentVertex !== 1)
        childNodesNum = this.adjacencyList[currentVertex].length - 1;
      this.adjacencyList[currentVertex].forEach((neighbor) => {
        if (!isVisited[neighbor]) {
          isVisited[neighbor] = true;
          if (obj[neighbor]) obj[neighbor] += percent / childNodesNum;
          else obj[neighbor] = percent / childNodesNum;
          queue.push(neighbor);
        }
      });
      percent /= childNodesNum;
    }
    return obj;
  }
}

const tree = new Tree();

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [N, W] = input.shift().split(" ").map(Number);
  for (let i = 1; i <= N; i++) {
    tree.addVertex(i);
  }
  for (let el of input) {
    const [v1, v2] = el.split(" ").map(Number);
    tree.addEdge(v1, v2);
  }
  const tempObj = tree.bfs(1);
  const percentArr = [];
  for (let vertex in tempObj) {
    if (tree.adjacencyList[vertex].length === 1)
      percentArr.push(tempObj[vertex]);
  }
  const answer =
    (percentArr.reduce((acc, cur) => acc + cur, 0) / percentArr.length) * W;
  console.log(answer);
});