[BOJ] 백준 [15681] 트리와 쿼리 JAVA

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

15681번: 트리와 쿼리

[문제]

[풀이]

탐색 + 다이나믹프로그래밍이 합쳐진 기초문제이다.
dfs를 한번 수행하여 leaf 노드에서 부터 재귀로 호출한 dfs가 종료 되기 전에 정점의 수를
메모이제이션 기법으로 기록해두고 , 쿼리가 호출될 때 dp 테이블 값을 바로 반환하는 것.

특정 노드 i의 자식정점의 갯수가 아니라 특정노드 i 를 포함한 정점을 반환해야함..

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static ArrayList<ArrayList<Integer>> tree;
    static int n,root,query;
    static int[] queryTable;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        n = input[0]; root = input[1]; query = input[2];
        tree = new ArrayList<>();
        for(int i=0;i<=n;i++) tree.add(new ArrayList<>());
        for(int i=0;i<n-1;i++){
            input = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            tree.get(input[0]).add(input[1]);
            tree.get(input[1]).add(input[0]);
        }
        queryTable = new int[n+1];
        visit = new boolean[n+1];
        dfs(root);
        while(query-->0){
            int q = Integer.parseInt(br.readLine());
            System.out.println(queryTable[q]);
        }
    }
 
    private static int dfs(int cur) {
        visit[cur]=true;
        int vertex=1;
        for (Integer next : tree.get(cur)) {
            if(visit[next]) continue;
            vertex+=dfs(next);
        }
        queryTable[cur]=vertex;
        return vertex;
    }
}