[BOJ 14267] 회사 문화1 (Java, DFS, Tree)

 

 

 

---

문제 링크

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

14267번: 회사 문화 1

---

문제 풀이

- 첫째 줄 회사 직원 수 n, 최초의 칭찬 횟수 m (2 ≤ n, m ≤ 100,000)

- 둘째 줄 직원 n명의 직속 상사(=부모 노드)가 주어짐, 최종적으로 1번이 사장(=Root)이다.

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

 

최대치 계산할 경우

- 직원 수(n) 1명에 칭찬(m) 100,000번을 칭찬의 수치(w) 1,000으로 했을 때 최대 10^8 이므로 Integer 범위

 

입력받은 직원의 칭찬 점수를 갱신하고, 순차 조회하면서 이전 노드의 칭찬 점수 누적해서 구하면 됨 

 

시간 복잡도 : O(N)

---

제출 코드

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

public class Main {   
    static StringBuilder sb = new StringBuilder();

    static int N, M, ROOT;

    static List<Integer>[] adj;

    static int[] PRAISE;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adj = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= N; i++) {
            int parent = Integer.parseInt(st.nextToken());
            if(i == 1) {
                ROOT = i;
                continue;
            }

            adj[parent].add(i);
        }

        PRAISE = new int[N + 1];
        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            PRAISE[to] += w;
        }

        br.close();
    }

    static void dfs(int node) {
        for(int employee : adj[node]) {
            PRAISE[employee] += PRAISE[node];
            dfs(employee);
        }
    }

    static void pro() {
        dfs(ROOT);

        for(int i = 1; i <= N; i++) sb.append(PRAISE[i]).append(" ");

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }


}