백준 1135 자바 - 뉴스 전하기

문제

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

코드

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

public class Main {
    private static List<Integer>[] tree;
    private static int[] dp;
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        dp = new int[n];
        tree = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            tree[i] = new ArrayList<>();
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        st.nextToken();
        for (int i = 1; i < n; i++) {
            tree[Integer.parseInt(st.nextToken())].add(i);
        }
        bw.write(String.valueOf(dfs(0)));
        bw.flush();
    }
    private static int dfs(int cur) {
        int cnt = 0, max = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (int 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;
    }
}

풀이

 tree에 인덱스가 상사의 번호인 부분에 1부터 순서대로 숫자를 집어 넣는다. 그 후 dfs라는 함수를 돌린다. tree의 인덱스 0부터 다 가져와 dp의 가져온 int형식의 번호 마다의 최댓값을 재귀함수를 통해 구한다. 그 후 q라는 우선순위 큐에 next, dp[next]를 넣는다. 번호와 그에 대한 최댓값을 넣는다. q에서 최댓값이 가장 큰 부분(가장 전파가 오래걸리는 부분) 부터 하나씩 가져와 cnt를 더한 값과 max와 비교해 최댓값을 저장한다. cnt는 1씩 늘려준다.(직속 부하에게 전화를 거는데 걸리는 시간) 최종적으로 dfs(0) 을 호출했던 값을 출력하면된다.