[백준 - 14267][GOLD 4][해설 X] - 회사 문화 1 (JAVA)

문제 링크

---

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

 

문제

---

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

직속 상사와 직속 부하관계에 대해 주어지고, 칭찬에 대한 정보가 주어질 때, 각자 얼마의 칭찬을 받았는지 출력하시오,

 

입력

---

첫째 줄에는 회사의 직원 수 n명, 최초의 칭찬의 횟수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000)

사장은 상사가 없으므로 칭찬을 받지 않는다.

 

출력

---

1번부터 n번의 직원까지 칭찬을 받은 정도를 출력하시오.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/*
	점화식) 
    현재 부하 직원이 받은 칭찬 = 현재 부하직원이 받은 칭찬 + 이전 부하직원이 받은 칭찬
*/

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        //그래프 초기화

        List<Integer> graph[] = new ArrayList[n+1];
		
        for(int i=0;i<graph.length;i++){
            graph[i] = new ArrayList<>();
        }

        int[] relation = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
        //그래프 갱신
        for(int i=1;i<relation.length;i++){
            graph[relation[i]].add(i+1);
        }

        int[] praise = new int[n+1];
		
        //처음을 칭찬을 받은 직원 갱신
        for(int k=0;k<m;k++){
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            praise[i]+=w;
        }
		
        //1번(사장) 부터 시작해서 부하 직원의 칭찬 갱신
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
	
        while(!q.isEmpty()){
            int curr = q.poll();

            for(int next : graph[curr]){
                praise[next] += praise[curr];
                q.add(next);
            }
        }

        //1번(사장) ~ n번 직원까지 칭찬 개수 출력
        StringBuilder sb = new StringBuilder();
		
        
        for(int i=1;i<praise.length;i++){
            sb.append(praise[i]+" ");
        }

        sb.deleteCharAt(sb.length()-1);

        System.out.println(sb);
    }
}

 

 

실행 결과

---

 

팁

---

• 누적합의 원칙을 트리에도 적용할 수 있다