백준 15681 트리와 쿼리 java

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/15681

2. 코드가 나오기까지 🛠️

1. 인접리스트 만들기

2. 부모가 누군지 확인하는 배열 만들기 (idx = 자식의 번호, value = 부모의 번호)

3. DFS를 타며 자신의 서브 트리 개수를 확인한다.
1. 기저 조건 = 서브 트리가 없을 경우 1반환
2. 계산
   자신의 자식의 서브트리 개수 모두 세어서 누적으로 더하기 및 그 최종 합을 반환

(1) 시간복잡도 분석 ⏳

3. 코드 🌐

import java.util.*;
import java.io.*;



public class Main {
    static int N,R,Q;
    static int [] parents;
    static int [] subTrees;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());
        parents = new int [N+1];
        subTrees = new int [N+1];
        for(int i = 0; i <=N; i++){
            list.add(new ArrayList<>());
        }
        for(int i = 0 ; i <=N; i++){
            parents[i] = i;
        }
        Arrays.fill(subTrees,1);
        for(int i = 0; i < N-1; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }
        findParents();
        dfs(R);
        StringBuilder ans = new StringBuilder();
        for(int i = 0 ; i < Q; i++){
            int query = Integer.parseInt(br.readLine());
            ans.append(subTrees[query]).append("\\n");
        }
        System.out.println(ans);
    }
    public static void findParents(){
        boolean [] check = new boolean [N+1];
        ArrayDeque<Integer> aq = new ArrayDeque<>();
        aq.add(R); check[R] = true;
        while (!aq.isEmpty()){
            int now = aq.poll();
            for(int i = 0; i < list.get(now).size(); i++){
                int next = list.get(now).get(i);
                if(check[next]) continue;
                check[next] = true;
                parents[next] = now;
                aq.add(next);
            }
        }
    }
    public static int dfs (int node){
        int cnt = 0;
        for(int i = 0; i < list.get(node).size(); i++){
            int next = list.get(node).get(i);
            if(next == parents[node]) continue;
            cnt += dfs(next)+1;
        }
        subTrees[node] = cnt+1;
        return cnt;
    }
}

4. 트러블 슈팅 or 배운 점📝