[백준] 1135. 뉴스 전하기 (트리/Java)

[백준] 1135. 뉴스 전하기

 

🤔 문제 핵심 이해

왜 최소 시간을 구해야 할까?

단순히 모든 직원에게 전화를 돌리면 간선의 수만큼 시간이 걸릴 것 같지만,

전화를 거는 순서에 따라 전체 소요 시간이 달라진다.

 

테스트케이스 2번 예시를 살펴보면

민식이행님(0)
├── 직원1
└── 직원2
    ├── 직원3
    └── 직원4

• 1번에게 먼저 전화하는 경우
  • 0 → 1 : 1분
  • 2 → 3 : 3분
  • 2 → 4 : 4분
  • 0 → 2 : 2분
  • 2번에게 전화할 때 이미 1분이 지나있고, 2번의 하위 직원들에게 전파하는 시간이 1분씩 지연됨
• 2번에게 먼저 전화하는 경우
  • 0 → 2 : 1분
  • 2 → 4 : 3분
  • 0 → 1 : 2분   |   2 → 3 : 2분
  • 2번이 하위 직원들에게 전파하는 동안 1번에게도 전화를 걸 수 있어서 더 효율적

시간이 오래 걸리는 부서부터 먼저 연락해야 전체 시간을 최소화할 수 있다.

 

📌 풀이 과정

1. 기본 아이디어

각 직원이 자신의 모든 부하에게 뉴스를 전파하는데 걸리는 최소 시간을 계산한다.

 

2. 재귀적 접근 (Bottom-Up)

1. 각 직속 부하의 전파 시간을 재귀적으로 계산
2. 시간이 오래 걸리는 부하부터 먼저 연락
3. 각 부하별 완료 시간 = 부하의 전파 시간 + 해당 부하에게 연락하는 순서
4. 모든 부하 중 가장 늦게 완료되는 시간이 답

3. 구체적인 계산 과정

어떤 직원의 직속 부하 3명의 전파 시간이 2, 2, 3분이라고 가정한다면

Step 1: 내림차순 정렬 → [3, 2, 2]

Step 2: 시간이 오래 걸리는 순서대로 연락

• 1번째 부하(3분): 3 + 1 = 4분 (1분째에 연락)
• 2번째 부하(2분): 2 + 2 = 4분 (2분째에 연락)
• 3번째 부하(2분): 2 + 3 = 5분 (3분째에 연락)

Step 3: 최댓값 선택 → max(4, 4, 5) = 5분

현재 직원이 자신의 모든 부하직원에게 뉴스를 전파하는데 걸리는 시간은 5분인 것이다!!

 

✨ 제출 코드

메모리: 14328KB

시간: 104ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int[] dp;
	static List<List<Integer>> employees;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		dp = new int[N];
		employees = new ArrayList<>();

		for(int i = 0; i < N; i++){
			employees.add(new ArrayList<>());
		}

		StringTokenizer st = new StringTokenizer(br.readLine());
		st.nextToken();
		for(int i = 1; i < N; i++){
			int parent = Integer.parseInt(st.nextToken());
			employees.get(parent).add(i); // 직속 부하 저장
		}

		System.out.println(dfs(0));
	}

	/**
	 * 현재 노드에서 모든 하위 노드에 소식을 전파하는데 걸리는 최소 시간을 계산
	 * 핵심 아이디어: 시간이 오래 걸리는 부하부터 먼저 연락해야 전체 시간이 최소가 됨
	 */
	private static int dfs(int cur){
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		for(int next : employees.get(cur)){
			dp[next] = dfs(next);
			pq.add(dp[next]);
		}

		// 시간이 오래 걸리는 부하부터 먼저 연락
		int time = 0, maxTime = 0;
		while(!pq.isEmpty()){
			int depth = pq.poll();
			time++;
			maxTime = Math.max(maxTime, depth + time);
		}

		return maxTime;
	}

}