BOJ 15681 : 트리와 쿼리

풀이 요약

루트 노드를 기점으로 한 완전탐색 DFS

풀이 상세

1. 입력 값으로 나오는 간선의 정보는 각각 부모노드, 자식노드인지 알 수 없는 상태이다. 따라서 일단은 양방향 그래프로 형성을 해주자.
2. 루트 노드를 시작으로, 모든 서브트리의 갯수를 구하는 값을 찾는다. 만약 임의의 노드 지나는 데 가지고 있는 자식 노드 중, 방문한 노드가 있다면 그 노드가 현재 노드의 부모 노드가 된다. 즉 그 노드를 뺀 나머지가 바로 해당 노드의 자식 노드들이다.
3. 해당 노드의 탐색이 모두 끝났을 때 현재까지의 서브 트리의 갯수를 배열 childCnt 의 인덱스에 넣어주자.
4. 알맞게 출력하면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static class Tree {
        int num;
        List<Tree> child = new ArrayList<>();

        Tree(int num) {
            this.num = num;
        }

        void push(Tree tree) {
            child.add(tree);
        }
    }

    static int N, R, Q;
    static Tree[] arr;
    static int[] childCnt,exp;
    static boolean[] visited;

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        stk = new StringTokenizer(br.readLine());
        N = Integer.parseInt(stk.nextToken());
        R = Integer.parseInt(stk.nextToken());
        Q = Integer.parseInt(stk.nextToken());

        arr = new Tree[N + 1];
        childCnt = new int[N + 1];
        visited = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = new Tree(i);
        }

        for (int i = 0; i < N - 1; i++) {
            stk = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(stk.nextToken());
            int n2 = Integer.parseInt(stk.nextToken());
            arr[n1].push(arr[n2]);
            arr[n2].push(arr[n1]);
        }

        exp = new int[Q]; // example
        for (int i = 0; i < Q; i++) {
            exp[i] = Integer.parseInt(br.readLine());
        }
    }

    private static int findChildCnt(Tree curr_tree) {
        visited[curr_tree.num] = true;

        int num = 1;
        for (Tree t : curr_tree.child) {
            if (visited[t.num]) continue;
            num += findChildCnt(t);
        }
        childCnt[curr_tree.num] = num;
        return num;

    }

    private static void output(int q) {
        for (int i = 0; i < q; i++) {
            System.out.println(childCnt[exp[i]]);
        }
    }

    public static void main(String[] args) throws Exception {
        input();
        findChildCnt(arr[R]);
        output(Q);
    }
}