[백준15681_자바스크립트(javascript)] - 트리와 쿼리

🔴 문제

트리와 쿼리

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\r\n');
const [n, r, q] = inputs[0].split(' ').map(Number);
const graph = Array.from({ length: n + 1 }, () => []);
const dp = Array(n + 1).fill(1); // 각 노드 자체도 서브트리에 포함된다.
const visited = Array(n + 1).fill(false);

for (let i = 1; i < n; i++) {
  const [u, v] = inputs[i].split(' ').map(Number);

  graph[u].push(v);
  graph[v].push(u);
}

const dfs = (node) => {
  visited[node] = true;

  for (const child of graph[node]) {
    if (!visited[child]) {
      dfs(child);
      dp[node] += dp[child];
    }
  }
};

dfs(r);

for (let i = n; i < inputs.length; i++) {
  const [u] = inputs[i];

  console.log(dp[u]);
}

🟢 풀이

⏰ 소요한 시간 : -

트리의 개념을 잘 설명해주는 문제다.
서브트리에 속한 정점의 개수를 출력해주는 문제인데 재귀적으로 서브트리를 순회하는 개념만 알고 있으면 어렵지 않게 풀 수 있다.

먼저 트리의 연결정보를 graph 배열에 넣어줬다. 문제에서 최상단 루트정보를 줬기 때문에 이 루트값을 가지고 dp 값을 구해주면 나머지 쿼리값에 대해 값을 금방 구할 수 있다.

dfs로 부모노드의 자식노드가 리프노드가 될 때까지 재귀호출을 해준다. 일단 dfs를 시작할 때 node 의 방문값을true로 바꿔준다.
그 후 현재 노드의 자식 노드들을 순회하면서 자식노드가 미방문 상태라면 dfs를 재귀호출하여 리프 노드를 찍고 나올 수 있도록 한다.
마지막으로 재귀를 마치고 나오면 현재 노드에 자식노드의 개수를 더해줘 dp 배열을 업데이트 해준다.

🔵 Ref