백준 14267번 회사 문화 1 (JAVA)

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

14267번: 회사 문화 1

 

저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 

저는 칭찬을 받고 바로 BFS를 돌리지 않고 scores에 각각의 직원들이 받은 칭찬을 저장했습니다. 

그리고 BFS를 통해 자신이 받은 칭찬의 수를 각각의 직속 부하에 더해주고, 각각의 직속 부하들도 자신이 처음에 받은 칭찬 + 상사에게 받은 칭찬을 각각의 직속부하들에게 전파하도록 구현하였습니다.

(칭찬이 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 시스템이라 위와 같이 생각했습니다.)

 

package BOJ.bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_14267 {
    private static final int NO_SENIOR = -1;
    private static final int CEO = 1;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int m = stoi.apply(st.nextToken());
        List<Integer>[] list = new List[n+1];
        for(int i = 1 ; i <= n ; i++){
            list[i] = new ArrayList<>();
        }
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++){
            int parent = stoi.apply(st.nextToken());
            if(parent == NO_SENIOR){
                continue;
            }
            list[parent].add(i);
        }
        int[] scores = new int[n+1];
        for(int i = 0 ; i < m ; i++){
            st = new StringTokenizer(br.readLine()," ");
            int employeeNo = stoi.apply(st.nextToken());
            int weight = stoi.apply(st.nextToken());
            scores[employeeNo] += weight;
        }
        bfs(list,scores,n);
        for(int i = 1 ; i <= n ; i++){
            System.out.print(scores[i]+" ");
        }
    }

    private static void bfs(List<Integer>[] list, int[] scores, int n) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {CEO,scores[CEO]});
        while(!q.isEmpty()){
            int[] now = q.poll();
            for(int next : list[now[0]]){
                scores[next] += now[1];
                q.offer(new int[] {next,scores[next]});
            }
        }
    }
}