아이디어

• DFS로 트리의 높이(DFS의 최대 깊이)를 탐색한다.
  • dfs() 메소드의 리턴값을 이용해 높이를 측정한다.
• 현재 노드에서의 트리의 높이(DFS의 최대 깊이)가 $D$보다 크다면 해당 경로로 갔다 돌아와야 하므로 답에 +2를 더한다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, S, D, ans;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static boolean[] visited;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		S = Integer.parseInt(tk.nextToken());
		D = Integer.parseInt(tk.nextToken());

		for (int i=0; i<=N; i++)
			graph.add(new ArrayList<>());
		
		for (int i=0; i<N-1; i++) {
			tk = new StringTokenizer(rd.readLine());
			int x = Integer.parseInt(tk.nextToken());
			int y = Integer.parseInt(tk.nextToken());
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		
		visited = new boolean[N+1];
		dfs(S);
		System.out.println(ans);
	}
	
	static int dfs(int v) {
		if (visited[v]) return 0;
		visited[v] = true;
		int d = 0;
		for (int n: graph.get(v)) {
			int result = dfs(n);
			if (result > D) ans += 2;
			d = Math.max(d, result);
		}
		return d + 1;
	}
}

메모리 및 시간

• 메모리: 70236 KB
• 시간: 568 ms

리뷰

• 문제에서 요구하는 사항을 잘 해석하기만 한다면 어렵지 않게 풀 수 있는 문제