[BOJ] 백준 [1135] 뉴스 전하기 JAVA

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

1135번: 뉴스 전하기

[문제]

[풀이]

일단 알아야 할 것은 상사는 아래 직원들 중에 가장 전파가 오래걸리는 직원한테 먼저 전파해야함.
가장 오래걸리는 기준은 직접 탐색하면서 찾아야 하는데 자식수가 많거나 깊이가 깊다고해서 오래 걸리는것은 아님.

탐색할 때 가장 오래걸리는 부하직원을 정렬하고
그 부하직원들에게 차례대로 카운트를 붙여 늘려준 합산이 (상사의 부하직원이 많을 수 있기때문)
상사가 선택할 직원이라는 것.

가령 , A 상사가 있고 B C D 부하직원이 있다고 가정을하자.
B=1 C=2 D=3 이면 당연히 D가 오래 걸리니 D한테 먼저 전파하면 된다.

하지만 A의 부하직원이 B~Z 까지 있고, B~Z 는 각자 모두 전파하는데 1밖에 안 걸린다고 가정을하면
A가 전파하는데 걸리는 시간은 부하직원의 수 만큼 걸릴 것이다.
다시 말해 , 부하직원의 수 만큼 카운트를 하는 이유이다.

코드를 보면 바로 이해가 가능하다.

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static ArrayList<Integer>[] tree;
    static int[] dp;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        tree = new ArrayList[n];
        dp = new int[n];
        for(int i=0;i<n;i++) tree[i] = new ArrayList<>();
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        for(int i=1;i<n;i++) tree[input[i]].add(i);
 
        System.out.println(dfs(0));
    }
 
    private static int dfs(int cur) {
 
        int cnt=0,max=0;
        Queue<int[]> q = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (Integer next : tree[cur]) {
            dp[next] = dfs(next);
            q.add(new int[]{next,dp[next]});
        }
 
        while (!q.isEmpty()){
            int[] node = q.poll();
            cnt++;
            max = Math.max(max,node[1]+cnt);
        }
 
        return max;
    }
}