[백준]19542: 전단지 돌리기(java)

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

19542번: 전단지 돌리기

문제

현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가 D$D$ 이하인 모든 노드에 전단지를 돌릴 수 있다.

날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

입력

첫번째 줄에는 노드의 개수 N$N$(1≤N≤100 000$ 1 \leq N \leq 100\ 000 $)과 케니소프트의 위치 S$S$(1≤S≤N$ 1 \leq S \leq N $), 힘 D$D$(0≤D≤N$ 0 \leq D \leq N $)이 주어진다.

두 번째 줄부터 N$N$번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 x$x$, y$y$가 공백으로 구분되어 주어진다. 이는 x$x$번 노드와 y$y$번 노드가 연결되어 있음을 의미한다. (1≤x,y≤N$1 \leq x, y \leq N$, x≠y$x \neq y$)

주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 1$1$이다.

출력

현민이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.

예제 입력 1 

6 1 1
1 2
2 3
2 4
3 5
5 6

예제 출력 1 

6

 

---

풀이

전체코드

package 백준;

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

public class BJ_G4_19542_전단지돌리기 {
    static ArrayList<Integer>[] graph;
    static int N, S, D;
    static int[] depth;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N+1];
        depth = new int[N+1];
        for(int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            graph[s].add(e);
            graph[e].add(s);
        }
        getChildrenCnt(S, 0);

        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (depth[i] >= D && i != S) {
                cnt++;
            }
        }
        System.out.printf("%d", cnt*2);
    }

    public static int getChildrenCnt(int now, int before) {
        int max = 0;
        for (int next : graph[now]) {
            if(next == before) continue;
            max = Math.max(max, getChildrenCnt(next, now) + 1);
        }
        depth[now] = max;
        return max;
    }
}