[백준] 19542: 전단지 돌리기 - JAVA

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

 

풀이

트리모양의 길 위에서 전단지를 돌리는데, 현재 노드에서 거리가 d이하인 노드들에는 현재 노드에서 전단지를 돌릴 수 있다.

 

따라서, 어떤 노드로부터 리프 노드까지의 거리가 d이하라면 더이상 앞으로 나아가지 않아도 된다는 것이다.

 

dfs탐색을 통해 리프까지의 최대 거리를 구한다. 해당 거리가 d이상이라면 `cnt`값을 늘려줬다.

 

다시 시작 정점으로 돌아와야 하므로 `cnt * 2`가 정답이 된다.

 

---

 

메모리: 70564KB
시간: 456ms
언어: Java 11

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

public class Main {
    static int s, d, cnt;
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        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());

            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        cnt = 0;
        visited = new boolean[n + 1];
        dfs(s);

        System.out.println(cnt * 2);
    }

    private static int dfs(int node) {
        visited[node] = true;

        int dist = 0;
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                dist = Math.max(dist, dfs(next));
            }
        }

        if (dist >= d && node != s) {
            cnt++;
        }

        return dist + 1;
    }

}