#백준_1135 뉴스 전하기 - Java

# 유형 : 탐색, DFS, 그리디

# 난이도 : 플래티넘 5

# 문제를 잘 못 이해해서 한참 걸렸다. 그렇게 생각하다 질문 게시판의 테스트 케이스를 보고 이해하였다.

아래의 테스트케이스 경우에 노드 1의 자식노드는 노드 2보다 많다. 하지만 그림을 그려보면 노드 1보다 노드 2가 깊이가 더 깊게 설계되어있다. 따라서 문제 해결 방식은 상사가 부하에게 전화할 때 가장 오래 걸리는 순으로 정렬한 후 전화를 걸어주면 된다.

1) 무조건 깊다고 그곳으로 들어가는 것이 아니다.

2) 노드 수가 많다고 무조건 그곳이 정답이 아니다.

3) 서브 트리 중 가장 오래 걸리는 순으로 정렬 후, 값을 더해주면서 체크하면 문제를 해결할 수 있다.

 

23

-1 0 1 1 1 2 2 2 3 3 3 4 4 4 0 14 15 16 17 18 19 20 21

 

package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class p1135 {
    static int N;
    static ArrayList<Point> arrList[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arrList = new ArrayList[N];
        for(int i=0; i<N; i++)
            arrList[i] = new ArrayList<>();
        
        st.nextToken();
        
        for(int i=1; i<N; i++) {
            int index = Integer.parseInt(st.nextToken());
            arrList[index].add(new Point(0, i));
        }
        System.out.println(solve(0));
    }
    
    private static int solve(int index) {
        // TODO Auto-generated method stub
        int result = 0; 
        for(int i=0; i<arrList[index].size(); i++) {
            int next = arrList[index].get(i).y;
            arrList[index].get(i).x = 1 + solve(next);
        }
//        for(Point po : arrList[index]) {
//            System.out.print(po.x+" "+po.y+" // ");
//        }System.out.println();
        Collections.sort(arrList[index]);
//        for(Point po : arrList[index]) {
//            System.out.print(po.x+" "+po.y+" // ");
//        }System.out.println();
        for(int i=0; i<arrList[index].size(); i++) {
            arrList[index].get(i).x += i;
            result = Math.max(result, arrList[index].get(i).x);
        }
        return result;
    }
 
    public static class Point implements Comparable<Point>{
        int x;
        int y;
        public Point(int x, int y) {
            this.x=x;
            this.y=y;
        }
        @Override
        public int compareTo(Point o) {
            if(x-o.x>0)
                return -1;
            else if(x-o.x<0)
                return 1;
            return x-o.x;
        }
        
    }
}