[백준 / BOJ] 15681 트리와 쿼리 (Java)

문제 

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

15681번: 트리와 쿼리

양방향 트리의 정점의 수 N

루트 번호 R

쿼리의 수 Q

가 주어진다.

 

각 쿼리를 입력받았을때, 해당 루트의 서브트리의 노드수를 구하는 문제다.

---

풀이

노드 N이 100000

쿼리 Q가 100000 이므로, 한 쿼리마다 모든 노드를 탐색하는 방식(완전탐색)으로 구현하면 시간초과가 난다.

 

쿼리를 입력받기전에, 한 정점을 루트로하는 서브트리가 갖고있는 노드의 수를 미리 전처리해놓으면, 매 쿼리마다 O(1)만에 구할수있으므로, O(N+Q)의 시간복잡도로 풀수있다.

 

전처리 하는 코드는 아래와 같다.

dp[node] = node를 루트로 하는 서브트리가 갖고있는 노드의 수

    private int initialDp(int node){
        if(dp[node] > 0) return dp[node];
        dp[node] = 1;
        for(int i = 0; i < edge.get(node).size(); i++){
            int nextNode = edge.get(node).get(i);
            if(dp[nextNode] > 0) continue;
            dp[node] += initialDp(nextNode);
        }
        return dp[node];
    }

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/15681%20%ED%8A%B8%EB%A6%AC%EC%99%80%20%EC%BF%BC%EB%A6%AC/Main.java

devxb/JJUNalgo