백준 14267 - 회사 문화 1

문제

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

리뷰

본래 유니온 파인드를 이용하여 접근했으나 입력값을 처리함에 있어 까다로운
부분이 있어서 트리를 그래프 형태로 표현하고 DFS를 통해 자식들의 reward를
갱신해주는 방식으로 로직을 구성하였다.

로직의 시간복잡도는 $O(N)$으로 수렴하므로 제한 조건인 2초를 무난히
통과할 수 있다.

코드

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

import static java.lang.Integer.parseInt;

public class Main {
    static int n, m;
    static List<Integer>[] parent;
    static int[] reward;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = parseInt(st.nextToken());
        m = parseInt(st.nextToken());

        parent = new List[n + 1];
        for (int i = 0; i < parent.length; i++)
            parent[i] = new ArrayList<>();
        reward = new int[n + 1];


        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < parent.length; i++) { // O(n)
            int root = parseInt(st.nextToken());
            if (root == -1) continue;

            parent[root].add(i);
        }

        while (m-- > 0) { // O(m)
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int value = parseInt(st.nextToken());

            reward[u] += value;
        }

        dfs(1); // O(n)
        for (int i = 1; i < reward.length; i++) // O(n)
            System.out.print(reward[i] + " ");

        br.close();
    }

    static void dfs(int root) { // O(N)
        for (int node : parent[root]) {
            reward[node] += reward[root];
            dfs(node);
        }
    }
}

결과