[백준OJ] 19542번 전단지 돌리기 - Java

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

19542번: 전단지 돌리기

---

풀이

먼저 시작점을 루트라고 생각하고 트리라고 생각해봅니다.

모든 노드를 기준으로 하는 서브트리의 최대 깊이를 구해줍니다.

그런 뒤, 시작지점 (루트) 를 기준으로 DFS를 돌며 거리를 구해줍니다.

1. 먼저 현재의 노드를 기준으로한 서브트리의 최대 깊이가 D와 같거나 작다면, 해당 노드에서는 이동할 필요가 없습니다.

2. 1번이 아닌 경우에는 다음과 같이 구해줍니다. 현재 노드를 시작점(루트)로 하는 서브트리라고 생각을 한 뒤, 모든 서브트리의 노드를 다녀오는 경우의 수를 구해줍니다. 

이 경우의 수는 다음과 같습니다.

[ (모든 자식들의 이동거리 합) + 자식의 수 * 2 ]

자식의 수 * 2 는 자식으로 들어가는 거리 1 + 자식으로부터 돌아오는 거리 1 = 2 이기 때문에 추가해주어야합니다.

 

이를 이용하여 문제를 해결해주었습니다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] depth;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
    static int answer = 0;
    static int makeDepth(int node){
        if(graph.get(node).size()==0){
            return depth[node]=1;
        }
        visited[node]=true;

        int maxDepth = 0;
        for(int child : graph.get(node)){
            if(!visited[child]) {
                visited[child]=true;
                int depth = makeDepth(child) + 1;
                maxDepth = Math.max(maxDepth, depth);
            }
        }

        return depth[node]=maxDepth;
    }

    static int dfs(int node,int D){
        visited[node]=true;
        if(depth[node]<=D){
            return 0;
        }
        int ret = 0;
        int cCount = 0;
        for(int child : graph.get(node)){
            if(visited[child]) continue;
            if(depth[child]>=D){
                cCount++;
                ret += dfs(child,D);
            }
        }
        return 2*cCount+ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.valueOf(st.nextToken());
        int S = Integer.valueOf(st.nextToken());
        int D = Integer.valueOf(st.nextToken());

        depth = new int[N+1];
        visited = new boolean[N+1];
        Arrays.fill(depth,0);

        for(int i=0;i<=N;i++) graph.add(new ArrayList<>());

        for(int i=0;i<N-1;i++){
            st = new StringTokenizer(br.readLine());
            int X = Integer.valueOf(st.nextToken());
            int Y = Integer.valueOf(st.nextToken());

            graph.get(X).add(Y);
            graph.get(Y).add(X);
        }

        makeDepth(S);
        Arrays.fill(visited,false);
        System.out.println(dfs(S,D));
    }
}