[java] 15681번 트리와 쿼리

1. 문제 링크 및 문제

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

2. 해결 방법 생각해보자 ...

루트노드에서부터 시작해서, 연결된 노드들의 수를 구하는 문제

---

예시

• 백준예시 1번 그래프
  
  (공통적으로 맨 처음에 들어가는 1 + 는 자기자신을 포함해야하므로 들어간 계산과정 )
  루트노드 5의 값은 어떻게 될까 ? 1 + 노드4 값 + 노드6값
  노드4 값은? 1 + 노드 3값
  노드3 값은? 1 + 노드1 값 + 노드 2값
  노드1 값은? 1 + 더할 자식노드 없으므로 => return 1
  노드2 값은? 1 + 더할 자식노드 없으므로 => return 1
  그럼 다시, 노드 3값은? 1+노드1값인 1 + 노드2값인 1 => return 3
  그럼 , 노드 4값은? 1+노드3값인 3 => return 4
  그리고, 노드6값도 똑같은 방식으로 구하면 노드5의 값은 9가 됩니다.

---

문제에서 입력의 수가 "트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)" 라는 어마어마하게 입력이 크므로, 우리는 dp의 메모이제이션 기법을 사용해야한다.

즉 노드3 값을 계산할 때 답은 1 + 노드1 값 + 노드2 값 이므로
dp[1]에 계산된 노드1의 값을 저장하고, dp[2]에도 계산된 노드2 값을 저장하고,
또 이걸 통해 계산된 노드3의 값을 dp[3] 에 저장해두어 다음 노드4 연산 때 활용하는 방식 으로 dp를 사용할 것이다.
이걸 코드로 구현!

노드4 연산 때 계산된 노드3을 활용하는 방식 은, 계산된 dp[3] 값은 0이 아닌 다른 숫자일테므로
dp[3] != 0 이 아니면, dp[3]값을 리턴하여 중복으로 구하는 경우도 방지한다.

3. 코드

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

public class Main {

	static int N,R,Q;
	static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
	static int[] dp;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());

		dp = new int[N + 1];
		
		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
		}
				
		for(int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int U = Integer.valueOf(st.nextToken());
			int V = Integer.valueOf(st.nextToken());
			list.get(U).add(V);
			list.get(V).add(U);

		}

		makeTree(R, -1); // 루트노드부터 시작

		StringBuilder sb = new StringBuilder();
		for(int i=0;i<Q;i++){
			int q = Integer.parseInt(br.readLine());
			sb.append(dp[q]).append("\n");
		}
		bw.write(sb.toString());
		bw.close();
		br.close();
	}

	public static int makeTree(int now, int parent){
    	// dp[now]가 계산된 경우
		if(dp[now]!=0) {
        	return dp[now];
        }

		dp[now] = 1; // 자기자신 +1 

		for(int child:list.get(now)){
			if (parent != child){
				dp[now] += makeTree(child, now);
			}
		}
		return dp[now];
	}
}