99클럽 3기 코테 스터디 12일차 TIL /[백준] 1135 뉴스 전하기 자바

 

 

 

 

 

 

1. 오늘의 학습 문제 

---

문제

---

 

 

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

뉴스 전하기

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

4576

2175

1807

48.575%

문제

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

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 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

예제 입력 3 복사

5
-1 0 1 2 3

예제 출력 3 복사

4

예제 입력 4 복사

24
-1 0 0 1 1 1 2 2 3 3 4 4 5 5 6 7 7 8 12 13 14 16 16 16

예제 출력 4 복사

7

 

 

 

 

 

 

 

코드

---

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];
		}
	}
}

 

 

 

 

 

2. 오늘의 회고

---

https://loosie.tistory.com/501

 

• 참고 블로그, 다시 풀어보려한다. 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL