[Java] 백준 1135번 : 뉴스 전하기

1. 문제

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

1135번: 뉴스 전하기

 

 

 

2. 풀이과정

1. 부모 정보를 배열에 받아서 저장한다.

2. 뒷번호부터 검사(leaf노드부터 검사하기 위함)

    1) 해당 숫자를 부모로 가진 자식들의 직간접적으로 이어진 자식들의 수를 구해서 정렬한다.

    2) 자식들 중 아래에 있는 자식들이 많은 것부터 차례로 순서를 부여한다.

    3) 순서 + 아래에 있는 자식들의 수가 가장 큰 값을 해당 숫자에 기록하며 업데이트 해간다.

 

 

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

public class Main {
	static int n, kids[];
	
	public static void updateKids(int kid, int[] p) {
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for(int i=0; i<n; i++) {
			if(p[i]==kid) {
				pq.add(kids[i]);
			}
		}
		int result = 0;
		for(int i=pq.size(); i>0; i--) {
			result = Math.max(result, i+pq.poll());
		}
		kids[kid] = result;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		kids = new int[n];
		int p[] = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			p[i] = Integer.parseInt(st.nextToken());
		}
		//
		for(int i=n-1; i>=0; i--) {
			updateKids(i, p);
		}
		System.out.println(kids[0]);
	}

}

 

결과