[백준 - 1135][GOLD 2][해설 X] - 뉴스 전하기 (JAVA)

문제 링크

---

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

 

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

 

해결 코드

---

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

/*
	부하직원이 자신의 모든 부하에게 뉴스를 전하는 시간이 큰 사람부터 상관이 뉴스를 전해야 최소값을 구할 수 있다.
    
    이때 한번에 한번씩 밖에 뉴스를 전하기 못하므로 다른 부하직원에겐 (현재까지 다른 부하직원에게 뉴스를 전한 횟수)만큼 추가 시간이 소요된다.
    
    그러므로 점화식은 다음과 같다
    
    i번째 상관이 뉴스를 전하는데 걸리는 시간
    = max(1번째로 큰 i번째 상관의 부하가 뉴스를 걸리는 시간 + 0,
          2번째로 큰 i번째 상관의 부하가 뉴스를 걸리는 시간 + 1,
          ...
          ,n번째로 큰 i번째 상관의 부하가 뉴스를 전하는데 걸리는 시간 + 자신보다 큰 부하직원의 수) 
*/

public class Main {
    static List<Integer> graph[];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        graph = new ArrayList[N+1];

        for(int i=0;i<=N;i++){
            graph[i] = new ArrayList<>();
        }

        int[]parent = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for(int i=1;i<parent.length;i++){
            graph[parent[i]].add(i);
        }

        int totalTime = getTotalCallTime(0);

        System.out.println(totalTime);
    }
	
    public static int getTotalCallTime(int curr){
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        int callTime = 0;
		
        //부하직원이 없으면 걸리는 시간도 없다
        if(graph[curr].isEmpty()){
            return 0;
        }
		
        //모든 부하의 부하직원에게 뉴스를 전달하는데 걸리는 시간 + 해당 부하직원에게 뉴스를 전달하는데 걸리는 시간(1분)
        for(int next : graph[curr]){
            pq.add(getTotalCallTime(next)+1);
        }

        int addTime = 0; //현재까지 전달한 부하직원의 수

        while(!pq.isEmpty()){
            callTime = Math.max(callTime,pq.poll() + addTime); //부하 중 오래 걸리는 시간이 curr직원이 걸리는 시간이다.
            addTime++;
        }

        return callTime;
    }
}

 

 

실행 결과

---

 

팁

---

• 트리를 이용한 최소값/최대값은 DP가 많다
• 트리를 이용한 DP는 bottom-top이 생각하기 쉽다.