[JAVA] 백준 1135 뉴스 전하기

 

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

 

문제분석

이 문제는 특이하게도, DFS를 진행하되 아래서부터 올라오는 Post-order DFS를 사용하면서&DP 를 활용한다.

 

뉴스를 전파할때, 아래처럼 전파에 4분 걸리는 구간과 1분 걸리는 구간이 있으면, 총 소요 시간은 4+1=5분이 아닌, 4분이다. 왜냐하면 4분이 소요되는 사원에 먼저 전파를 했다고 해도, 4분이 끝날 때 까지 기다리는 것이 아니라 다른 사원에게 전파를 할 수 있기 때문이다.

하지만 특정한 [조건]이 추가되어야 한다. 한번에 한 명에게 전파할 수 있기 때문에, 현재시간+자식 노드 소요시간>최대 시간 후보 라는 조건이다.

부모 노드에 뉴스가 도달하였을 때, 1분에 한명에게만 뉴스를 전파할 수 있다.  최소 시간을 구하기 위해선 이 1명을, 소요시간이 가장 큰 사람에게 줘야 한다(그림에서 4와 1 중에 4에 해당). 이때, 이 사람의 소요시간이 부모 소요시간-1의 후보가 된다(부모에게 전달해주는 시간 1을 제외하고, 자식의 총 소요시간을 구해야 하기 때문). 그럼 소요시간 최대값이 답인 것인가? 아니다. 여기에는 큰 예외가 숨어있다.

예를들어, 1, 2, 3, 3, 5 의 소요시간을 가진 자식 노드들이 있다고 가정하자. 후보는 5 부터 시작한다. 그러나, 여기서 가운데 3에 뉴스를 전달해 줄 때를 보자. 분명 5보다 작지만, 시작 시간이 3분이다. 따라서 총 소요 시간은 6분이 된다. 이점을 감안해서 현재 시간+자식 소요 시간이 후보 시간보다 큰 경우에는 후보 시간이 교체된다.

 

DP를 활용한다고 말했었는데, 이 문제의 최적 부분 해로는, "해당 노드의 소요 시간은, 하위 노드들의 소요 시간 중 [조건]을 만족하는 최대값"이다. 이를 리프 노드부터 차례대로 진행하면, 루트 노드의 소요 시간까지 같은 원리로 구할 수 있다.

 

코드

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

public class Main{
    public static Map<Integer,ArrayList<Integer>> tree;
    public static int result;
    public static int[] cost;
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        tree = new HashMap<>(); // key에 노드, arraylist에 자식 노드
        cost = new int[N];

        st.nextToken();
        for(int i = 1; i < N; i++){ // 1부터 N-1까지 탐색
            int child = i;
            int root = Integer.parseInt(st.nextToken());

            tree.computeIfAbsent(root,k->new ArrayList<Integer>());
            tree.get(root).add(child);
        }
        DFS(0);
        System.out.println(cost[0]-1);
    }
    public static void DFS(int node){
        ArrayList<Integer> ar;
        if(tree.containsKey(node)){// 리프 노드가 아니라면
            ar = tree.get(node);
            for(int i=0;i<ar.size();i++){
                DFS(ar.get(i));
            }
        }else{ // 리프인 경우, 전달에 걸리는 시간은 1분
            cost[node] = 1;
            return;
        }

        ArrayList<Integer> childCosts = new ArrayList<>();
        for (int child : ar) {
            childCosts.add(cost[child]);
        }
        
        Collections.sort(childCosts, Collections.reverseOrder());

        int childMax = childCosts.get(0);
        if(childCosts.size()>1){
            for(int i = 1; i < childCosts.size(); i++){ // 1 2 3 3 5 라면, 여기서 걸리는 시간은 5가 아니라 6임. 또한, 마지막에 1 추가해야함(현재노드 할당시간 1분)
                if(i + childCosts.get(i) > childMax){ // 지나간 시간+사용해야 하는 시간이 최대 시간보다 큰 경우
                    childMax = i + childCosts.get(i);
                }
            }
        }
        cost[node] = childMax + 1;
    }
}