백준 15681번: 트리와 쿼리 [그래프][트리][재귀] -Java

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

15681번: 트리와 쿼리

연습문제

 

루트부터 리프까지 탐색하며 현재 자식노드의 개수를 리턴한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static List<Integer>[] tree;
	public static int[] ans;
	public static boolean[] visit;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		ans = new int[N+1]; //1~N
		tree = new ArrayList[N+1];
		visit = new boolean[N+1];
		
		for (int i = 1; i <= N; i++) {
			tree[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int U = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			
			tree[U].add(V); //무방향 그래프이므로 양쪽에 모두 추가
			tree[V].add(U);
		}
		
		//정점U를 루트로 하는 서브트리 정점의 수 구하기
		ans[R] = fun(R);
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		for (int i = 0; i < Q; i++) {
			int que = Integer.parseInt(br.readLine());
			bw.write(ans[que]+"\n");
		}
		bw.flush();
	}

	public static int fun(int root) {
		visit[root] = true;
		
		//자식노드가 없다면 내 정점만 카운팅하여 1을 리턴한다.
		if(tree[root].size()<0) 
			return 1; 
		
		for (int i = 0; i < tree[root].size(); i++) {
			
			int child = tree[root].get(i);
			//위에서부터 내려오므로 들른 곳은 무조건 나의 부모노드이다.
			if(visit[child])
				continue; 
			
			ans[root]+=fun(child);
		}
		
		ans[root]++; //현재 자기자신 정점도 포함할 것
		return ans[root];
	}
}