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

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

 

풀이

상사가 직속 부하를 칭찬할 수 있는데 a가 b에게 10의 칭찬을 했다면 b의 직속 부하인 c도 10의 칭찬을 받는 것이 된다.

각 번호의 직원마다 직속 상사의 번호가 주어져 저장했다.

직속 상사로부터 칭찬을 받은 직원의 번호와 칭찬 수치가 주어지는데, int배열을 만들어 저장했다.

1번이 사장이므로 1번부터 시작하여 트리를 타고 내려가면서 int배열의 값을 부모 노드에서 자식 노드에 더해주는 식으로 구현했다.

 

---

 

메모리: 76068KB
시간: 792ms
언어: Java 11

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

public class Main {
    static ArrayList<ArrayList<Integer>> list;
    static int[] score;
    static boolean[] visited;

    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());
        list = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            list.add(new ArrayList<>());
        }

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

        score = new int[n + 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());
            score[idx] += w;
        }

        visited = new boolean[n + 1];
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                bfs(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < n + 1; i++) {
            sb.append(score[i] + " ");
        }

        System.out.println(sb);
    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : list.get(node)) {
                visited[next] = true;
                score[next] += score[node];
                queue.add(next);
            }
        }
    }

}