백준 15681: 트리와 쿼리 - javascript(트리, dfs)

문제 출처

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

 

정답 풀이 

뭘 구하라는건지 이해가 안갔는데, 

서브트리 개수를 구하는 문제이다. 

 

 

뜬금없이 쿼리? 이랬는데, 해당 문제에서 쿼리는 5,4,8 의 서브트리를 구하라는 3개의 쿼리가 있다. 

 

서브트리는 뭘까?

=> 해당 노드를 루트로 하고, 그 아래 속하는 모든 자식 노드들을 포함하는 트리이다. ! 

 

 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,r,q] = input[0].split(' ').map(v => +v)
const graph = Array.from({length: n+1}, () => []); 
for(let i=1; i<n; i++){
    const [u,v] = input[i].split(' ').map(v => +v); 
    graph[u].push(v); 
    graph[v].push(u)
}

const queries = []; 
for(let i=n; i<n+q; i++){
    queries.push(Number(input[i]))
}

const subtree = Array(n+1).fill(0)
const visited = Array(n+1).fill(false)

function dfs(node){
    visited[node] = true;
    subtree[node] = 1; 
    
    for(const next of graph[node]){
        if(!visited[next]){
            subtree[node] += dfs(next)
        }
    }
    return subtree[node]
}

dfs(r);

const results = queries.map(query => subtree[query])
console.log(results.join('\n'))