[BOJ] 백준 1135번 뉴스 전하기 (Java)

#1135 뉴스 전하기

난이도 : 골드 1

유형 : 그리디 / 트리 DP

1135번: 뉴스 전하기

▸ 문제

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

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

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

▸ 입력

첫째 줄에 직원의 수 N이 주어진다. 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다. 반드시 0번 직원 (오민식)의 상사는 -1이고, -1은 상사가 없다는 뜻이다. N은 50보다 작거나 같은 자연수이다.

▸ 출력

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

 

문제 풀이  

단순하게 생각하면 트리 후위순회로 리프노드부터 DP를 사용하면 차근차근 계산하면 될 것 같은데 뚜렷한 경로가 보이지 않는다. 그래서 완전탐색보다는 최적의 경로를 세워 그리디 탐색을 해줘야 한다. 

 

그리디는 지금 가장 최선의 선택을 해야하므로 현재 노드의 서브 트리에서 어떤 노드로 먼저 진출할지를 결정해야 한다. 

 

1. 트리의 크기 순(자식 수가 많은 트리)대로 탐색한다. 
2. 트리의 depth가 깊은 순대로 탐색한다.

 

어떤 서브트리를 선택할까

 

이를 결정하려면 문제의 탐색 방식을 한번 더 살펴보면 1번 케이스의 반례를 찾을 수 있다.

• sub1트리의 크기는 6이고, depth는 4이다.
• sub2트리의 크기는 5이고, depth는 5이다.

1번 트리 크기순(왼), 2번 depth 순(오른)

 

1번 방식으로 그리디 탐색을 할 경우, sub1트리는 4초만에 탐색이 가능하지만 sub2트리는 2초부터 시작하기 때문에 6초에 끝이난다. 반면 2번 방식으로 그리디 탐색을 할 경우, sub1트리는 2초에 탐색해도 총 3초가 걸리기 때문에 5초에 끝나고, sub2트리도 5초에 끝나므로 최소 시간에 도착하는 것을 확인할 수 있다.

 

결국은, 그리디 알고리즘 기본 예제인 도시락 먼저 데우기 방식(먹는데 오래 걸리는 음식을 먼저 데운다.)과 같이 탐색이 가장 오래 걸리는(depth가 가장 깊은)트리 부터 먼저 탐색하는 것이 최적해를 포함하는 것을 알 수 있다.

 

+ 위의 예제 샘플은 다음과 같다.

12

-1 0 0 1 1 2 4 4 5 7 8 10 11

설계

그럼 이제 코드를 설계해주면 되는데 위의 오른쪽 트리 과정을 보며 구현하면 이해하기 쉽다.

1. 후위순회를 통하여 각 노드를 탐색한다. depth가 줄어들 때 마다 dp[부모노드]에 +1초를 더해준다.
   1. dp[nxt] = 1+ solve(nxt);
2. 현재노드(idx)의 자식노드들을 깊이 순대로 정렬한 후 탐색한다. (깊이가 깊음 = 해당 부모노드 까지 오는데 시간이 더 걸렸음)
   1. 깊이 순대로 탐색하기 때문에 차례대로 i: (0~idx자식노드 수-1)초를 더해준다. (1번에서 1초 더해주기 때문에 0초부터 시작)
   2. for(int i=0...list[idx].size()-1) dp[num] +=i;
3. 위의 방식을 반복하여 최종적으로 여러개의 서브트리 중 가장 오래걸린 시간을 출력해준다.
   1. res = Math.max(res, dp[num])

 

풀이 코드 

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

public class Main {

	static List<Integer>[] list;
	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		list = new ArrayList[n];
		int rt=0;
		dp = new int[n];
		for(int i=0; i<n; i++) {
			list[i] = new ArrayList<>();
			int a = Integer.parseInt(st.nextToken());
			if(a==-1) {
				rt=i;
			}else {
				list[a].add(i);	
			}
		}
		int min = solve(rt);
		System.out.println(min);
	}
	
	static int solve(int idx) {
		for(int nxt : list[idx]) {
			dp[nxt] = 1+ solve(nxt);
		}
		Collections.sort(list[idx], new DepthComp());
		int res =0;
		for(int i=0; i<list[idx].size(); i++) {
			int num = list[idx].get(i);
			dp[num] +=i;
			res = Math.max(res, dp[num]);
		}
		return res;
	}
	
	static class DepthComp implements Comparator<Integer>{
		@Override
		public int compare(Integer o1, Integer o2) {
			// TODO Auto-generated method stub
			return dp[o2]-dp[o1];
		}
	}
}