백준 - 14267 회사 문화 1(Java)

구현 문제입니다.

 

회사원 n, 칭찬 횟수 m이 첫 번째 줄에서 주어집니다.

두 번째 줄은 1번 회사원 부터 직속 상사의 번호가 주어집니다.

 

이 말을 반대로 생각하면 주어지는 값의 인덱스가 직속 후배라는 뜻입니다.

-1, 1, 2, 3, 4 가 주어진다고 하겠습니다.

 

인덱스 1번의 값은 -1입니다. 최상위 상사인 것을 알 수 있습니다.

인덱스 2번의 값은 1입니다. 2번의 직속 상사는 1번이자, 1번의 직속 후배는 2번으로 해석할 수 있습니다.

인덱스 3번의 값은 2입니다. 3번의 직속 상사는 2번이자, 2번의 직속 후배는 3번으로 해석할 수 있습니다.

인덱스 3번의 값은 4입니다. 4번의 직속 상사는 3번이자, 3번의 직속 후배는 4번으로 해석할 수 있습니다.

인덱스 4번의 값은 5입니다. 5번의 직속 상사는 4번이자, 4번의 직속 후배는 3번으로 해석할 수 있습니다.

 

세 번째 줄은 칭찬받는 후배와 그 값이 주어집니다.

count[] 배열에 값을 저장시킨 다음, 직속 후배를 Queue에 넣어 반복하면 끝나는 문제입니다.

 

[구현 코드]

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

public class Main {
    private static int[] counts;
    private static Map<Integer, List<Integer>> map;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz= new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(stz.nextToken());
        int m = Integer.parseInt(stz.nextToken());
        counts = new int[n +1];

        stz = new StringTokenizer(br.readLine(), " ");

        map = new HashMap<>();
        for(int i=0; i<n+1; i++){
            map.put(i, new ArrayList<>());
        }

        for(int i = 0; i< n; i++){
            int p = Integer.parseInt(stz.nextToken());
            if(p == -1){
                continue;
            }

            List<Integer> elements = map.getOrDefault(p, new ArrayList<>());
            elements.add(i+1);
            map.put(p, elements);
        }

        for(int i = 0; i< m; i++){
            stz = new StringTokenizer(br.readLine(), " ");
            int k = Integer.parseInt(stz.nextToken());
            int w = Integer.parseInt(stz.nextToken());
            counts[k] += w;
        }

        for(int i=1; i<n+1; i++){
            // i의 후배
            Queue<Integer> qu = new LinkedList<>(map.get(i));

           // i의 후배의 후배
            while (!qu.isEmpty()){
                int c = qu.poll();
                counts[c] += counts[i];
            }
        }

        Arrays.stream(counts, 1, counts.length)
                .forEach(e -> {
                    try {
                        bw.write(e + " ");
                    } catch (IOException ioException) {
                        ioException.printStackTrace();
                    }
                });

        bw.flush();
        bw.close();
        br.close();
    }
}