[백준/JAVA] BOJ 14267 - 회사 문화 1

오랜만에 마음을 다시 다잡으며 시작하는 알고리즘

👀 문제

14267번: 회사 문화 1 ✨ 골드 4

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

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

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

예제 입력

5 3
-1 1 2 3 4
2 2
3 4
5 6

예제 출력

0 2 6 6 12

🔑 키포인트

깊이 우선 탐색

✍️ 코드

📍 dfs를 이용해 탐색하면서 점수를 더해 주면 되는 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class BOJ14267_회사문화1 {
    static int[] answer;
    static ArrayList<ArrayList<Integer>> graph;

    public static void main(String[] args) throws IOException {
        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());
        answer = new int[n + 1];
        graph = new ArrayList<>();

        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int boss = Integer.parseInt(st.nextToken());
            if (boss != -1) {
                graph.get(boss).add(i + 1);
            }
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            answer[idx] += w;
        }

        dfs(1);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < n + 1; i++) {
            sb.append(answer[i] + " ");
        }
        System.out.println(sb.toString());
    }

    static void dfs(int idx) {
        for (int next : graph.get(idx)) {
            answer[next] += answer[idx];
            dfs(next);
        }
    }
}