백준 - 19542 전단지 돌리기(Java)

dfs 문제입니다.

 

트리 형태의 맵에서 전단지를 돌렸을 때, 최소로 방문하게 되는 길의 거리를 구하는 문제입니다. 

단, 주의 해야할 점이 있습니다.

이 문구를 해석하면 다음과 같습니다.

리프 노드에서 거리가 D인 거리 까지만 탐색하면된다.

위 그림에 의하면 리프노드인 4번과 6번에서 거리가 1인 2번과 5번 까지만 탐색을 하면 되는 것입니다.

단, 5번 노드를 갈 때 2번 노드를 거치기 때문에 이를 중복해서 계산하지 않게 합니다.

 

[구현 코드]

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    private static List<List<Integer>> graph;
    private static int n, s, d, answer;
    private static int[] depth;
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stz.nextToken());
        s = Integer.parseInt(stz.nextToken());
        d = Integer.parseInt(stz.nextToken());

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

        for(int i=0; i<n-1; i++){
            stz = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        depth = new int[n+1];
        visited = new boolean[n+1];
        dfs(s);

        // 왕복
        bw.write(String.valueOf(answer*2));

        bw.flush();
        bw.close();
        br.close();
    }

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

        for(int i=0; i<graph.get(node).size(); i++){
            int next = graph.get(node).get(i);

            if(!visited[next]){
                depth[node] = Math.max(depth[node], dfs(next)+1);
            }
        }

        // 거리가 d 이상인 것만 들림
        if(node != s && depth[node] >= d){
            answer++;
        }

        return depth[node];
    }
}