백준 14267번 내리 칭찬 java

자신의 직속 상사 순서대로 연결을 하면 내리 칭찬이기 때문에 트리 형태가 나타나게 된다.

자신을 칭찬하는 숫자를 연결된 트리의 자식으로 쭉쭉 내리면 된다.

이번엔 시간 초과가 발생함....//해결 방법은 아래

시간초과가 발생할 수 있었던 부분은 바로 한쪽으로 편향된 트리인데 편향된 트리에서 최종보스 바로 밑에 있는 부하에게 칭찬(또는 갈굼)을 계속적으로 하는 경우이다. 그럴 경우 굉장히 깊이 있는 트리 끝까지 방문해야 하기 때문에 시간초과가 났던것이다.

예를들어 깊이가 100000인 트리에서 2번 직원에게만 100000번의 칭찬을 한다고 가정하면 트리노드를 방문하는 숫자는 100000*100000 이기때문에 10,000,000,000번 즉 100억번을 방문해야 하며, 이것은 1초에 1억번 계산하는 컴퓨터라고 하여도 100초가 걸리게 된다.

따라서 각 칭찬의 시작점을 모두 한번에 계산하고 칭찬을 시작하지 않는 직원은 모두 무시한다.

package com.company;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.logging.FileHandler;

public class Main {
    static int[] totalPrice;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        totalPrice = new int[N];
        int[] PriceList = new int[N];

        String temp = br.readLine();
        st = new StringTokenizer(temp);

        ArrayList<ArrayList> mans= new ArrayList<>();
        for(int i=0;i<N;i++){
            ArrayList<Integer> tempList = new ArrayList<>();
            mans.add(tempList);
        }//인접리스트 생성

        int stringNum=0;

        while (st.hasMoreTokens()){
            if(stringNum==0){
                stringNum++;
                st.nextToken();
            }else{
                mans.get(Integer.parseInt(st.nextToken())-1).add(stringNum);
                stringNum++;
            }
        }//자신의 상사를 리스트에 추가함
        Deque<Integer> deque = new ArrayDeque();

        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine());
            PriceList[Integer.parseInt(st.nextToken())-1]+=Integer.parseInt(st.nextToken());
        }//칭찬의 시작점을 한번에 저장
        for(int i=0;i<N;i++){
            if(PriceList[i]==0){
                continue;
            }//칭찬을 시작하지 않는 지점은 패스
            totalPrice[i]+=PriceList[i];
            int value = PriceList[i];
            for(int j=0;j<mans.get(i).size();j++){
                deque.add((Integer) mans.get(i).get(j));
            }
            while (!deque.isEmpty()){
                int point = deque.poll();
                totalPrice[point]+=value;
                for(int j=0;j<mans.get(point).size();j++){
                    deque.add((Integer) mans.get(point).get(j));
                }
            }
        }//BFS로 하든 DFS로 하든 상관은 없지만 DFS로 하면 백트래킹을 이용해야 한다.

        for(int item : totalPrice){
            bw.write(Integer.toString(item));
            bw.write(" ");
        }//출력하며 함수 종료
        bw.flush();
        bw.close();
    }
}