BOJ 1135 뉴스 전하기

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

문제

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

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

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

---

입력

첫째 줄에 직원의 수 N이 주어진다. 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수이다. N은 50보다 작거나 같은 자연수이다.

---

출력

첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력한다.

---

예제 입력 1

3
-1 0 0

예제 출력 1

2

예제 입력 2

5
-1 0 0 2 2

예제 출력 2

3

… 이하 예제 생략

---

코드

처음 문제를 풀었을 때, 별 생각 없이 그냥 직속 부하 직원이 많은 직원에게 먼저 소식을 전해 걸리는 시간을 계산했다.

하지만, 조금만 더 생각해보면 특정 직원의 직속 부하가 많다고 해서 그 직원의 모든 부하 직원에게 소식을 전하는 시간이 오래 걸리는 것이 아니라는 것은 알 수 있다.

조금 더 고민해 보고 Top-down 방식으로 문제를 해결할 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;

    // 상사 직속 부하 직원들의 목록을 저장하기 위한 배열, ex) junior[0]은 0번 직원의 직속 부하 직원들의 List
    static List<Integer>[] junior;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        junior = new List[N];
        for (int i = 0; i < N; i++) {
            junior[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        st.nextToken();
        for (int i = 1; i < N; i++) {
            int senior = Integer.parseInt(st.nextToken());

            junior[senior].add(i);
        }

        int answer = calculateMinTime(0);

        System.out.println(answer);
    }

    /**
     * 직원이 모든 직간접 부하 직원에게 소식을 전하는데 걸리는 최소 시간을 계산하는 메소드
     * @param senior 검사하려는 직원
     * @return 모든 직간접 부하 직원에게 소식을 전하는데 걸리는 최소 시간
     */
    static int calculateMinTime(int senior) {
        // 부하 직원이 없으면 소식을 전하는데 걸리는 시간은 0
        if(junior[senior].size() == 0) {
            return 0;
        }

        // 직속 부하들이 소식을 전하는데 걸리는 최소 시간들을 구함
        PriorityQueue<Integer> times = new PriorityQueue<>(Comparator.reverseOrder());

        for (int check: junior[senior]) {
            int timeOfJunior = calculateMinTime(check);

            times.offer(timeOfJunior);
        }

        // 소요 시간 중 오래 걸리는 순서로 직속 부하에게 소식을 전하며 걸리는 시간을 측정
        int time = 0;
        int queueSize = times.size();
        for (int i = 0; i < queueSize; i++) {
            time = Math.max(time, times.poll() + i);
        }

        return time + 1;
    }
}