뉴스 정하기

0. 문제 링크

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

1135번: 뉴스 전하기

---

1. 문제 핵심

1. 민식이의 회사는 트리 구조이다. 
2. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 
3. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.
4. 민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 
5. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 
6. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 
7. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오. 오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

---

2. 문제 접근

1.  

---

3. 코드 분석

---

4. 베스트 코드 분석

---

5. 코드

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

public class Main {
	static class Reader {
		final private int BUFFER_SIZE = 1 << 3;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[BUFFER_SIZE]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					if (cnt != 0) {
						break;
					} else {
						continue;
					}
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	static class CustomComparator implements Comparator<Integer> {
		@Override
		public int compare(Integer o1, Integer o2) {
			// TODO Auto-generated method stub
			return o2 - o1;
		}
	}

	public static void main(String[] args) throws IOException {
		Reader br = new Reader();
		// 총 노드 개수
		int N = br.nextInt();

		// 자신의 값에 전달 시간을 더한 값을 부모에게 알려주기 위해 알려주기 위해 부모 자리에 자식 값을 저장하는 우선 순위 큐
//		PriorityQueue<Integer>[] arr = new PriorityQueue[N + 1];

		// 초기화
//		for (int i = 0; i <= N; i++) {
//			arr[i] = new PriorityQueue<>((o1, o2) -> o2 - o1);
//		}
		int[] v = new int[N + 1];
		Map<Integer, PriorityQueue<Integer>> pSaveC = new HashMap<>();

		// 자식으로부터 부모를 알아낼 수 있음
		Map<Integer, Integer> cToP = new HashMap<>();
		int prnt = 0;
		// -1은 제외
		br.nextInt();
		PriorityQueue<Integer> tmp;
		// 각 자리 입력을 반복
		for (int i = 1; i < N; i++) {
			// 부모 입력
			prnt = br.nextInt();
			// 부모가 없다면 새로 생성
			if (!pSaveC.containsKey(prnt)) {
				tmp = new PriorityQueue<>((o1, o2) -> o2 - o1);
				tmp.add(i);
				pSaveC.put(prnt, tmp);

			} else {
				tmp = pSaveC.get(prnt);
				tmp.add(i);
				pSaveC.put(prnt, tmp);
			}
			// 자식의 부모가 누구인지 저장
			cToP.put(i, prnt);
		}
		int max = 0, cnt = 1;
		PriorityQueue<Integer> childrens;
		int child;
		Integer[] childV;
		// 마지막부터 루트 전까지 반복
		for (int i = N - 1; i >= 0; i--) {

			// 부모가 저장되어 있을 때
			if (pSaveC.containsKey(i)) {
				max = 0;
				// 가장 큰 자식 값부터 빼준 뒤
				childrens = pSaveC.get(i);
				cnt = 0;
				childV = new Integer[childrens.size()];
				while (!childrens.isEmpty()) {
					child = childrens.poll();
					childV[cnt] = v[child];
					cnt++;
				}
				cnt = 1;
				Arrays.sort(childV, Collections.reverseOrder());
				for (int j = 0; j < childV.length; j++) {
					max = Math.max(max, childV[j] + cnt);
					cnt++;
				}
				v[i] = max;
			}
		}
		System.out.println(v[0]);
	}
}