백준 19542 - 전단지 돌리기

[문제 바로가기]

 

1. 유형

깊이 우선 탐색, 트리

 

2. 문제 접근

2-1. 해설

우선 저는 현재 위치와 leaf노드까지의 깊이를 탐색했습니다.

그림-1

그림 1처럼 만드는 것은 재귀를 사용해서 return값에 +1을 해주면 됩니다.

 

하지만 저기서도 문제가 있습니다.

2,3,4 노드 같은 여러 가지로 뻗어나가는 부분이 까다롭습니다.

그림2

그래서 그림2 처럼 여러 가지로 뻗어나가는 경우는 리턴 값 중 최댓값을 노드의 깊이로 선택하면 됩니다.

 

그림 1처럼 노드의 최대 깊이를 탐색했으면 D보다 큰 녀석들의 갯수를 카운트해주고, 왕복이니깐 *2를 해주면 정답이 나옵니다.

 

2-2. 설계

3. 코드

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

public class Main {
	static boolean visit[];
	static int N,M,D,dp[];
	static List<Integer> list[];
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M= stoi(st.nextToken());
		D= stoi(st.nextToken());
		list= new ArrayList[N+1];
		visit=  new boolean[N+1];
		dp = new int[N+1];
		for(int i=0; i<=N; i++) {
			list[i]=new ArrayList<>();
		}
		for(int i=0; i<N-1; i++) {
			st = new StringTokenizer(in.readLine());
			int a=stoi(st.nextToken());
			int b=stoi(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		visit[M]=true;
		dfs(M);
		int ans=0;
		for(int i=1; i<=N; i++) {
			if(i!=M && dp[i]>=D) {
				ans++;
			}
		}
		System.out.println(ans*2);
	}
	static int dfs(int node) {
		int val=0;
		for(int next: list[node]) {
			if(!visit[next]) {
				visit[next]=true;
				val=Math.max(val, dfs(next));
			}
		}
		dp[node] = val;
		return dp[node]+1;
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}