[백준 14267] 회사 문화 1 (C++)

문제 링크: www.acmicpc.net/problem/14267

14267번: 회사 문화 1

1. 주의할 점

- 한명의 상사에겐 여러명의 직속부하가 있을 수 있다

- 칭찬을 모두 저장했다가 트리의 순서에 따라 부여한다

 

2. 구현

- 모든 직원들에 대해 상사->직속 부하에 대한 정보를 V[]벡터에 저장한다

- 입력받은 모든 칭찬에 대해 해당 직원의 index번호에 해당하는 Compliment[]에 더한다(한 직원이 여러번 받았을 수도 있으므로 할당이 아닌 더하기)

- 사장인 1번부터 시작하여 Queue에 넣고 bfs 탐색을 수행한다

- 상사의 직속부하들에게 상사가 부여받은 칭찬만큼 더해주고, 부하의 번호를 Queue에 추가하여 작업을 반복한다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[100001];
int compliment[100001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num, query,val,a;
    cin >> num >> query;
    for(int i=1;i<=num;i++){
        cin>>val;
        if(i==1) continue;
        v[val].push_back(i);
    }
    for(int i=0;i<query;i++){
        cin>>a>>val;
        compliment[a]+=val;
    }
    priority_queue<int,vector<int>,greater<int>> pq;
    pq.push(1);
    while(!pq.empty()){
        int cidx = pq.top();
        pq.pop();
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i];
            compliment[next]+=compliment[cidx];
            pq.push(next);           
        }
    }
    for(int i=1;i<=num;i++)
        cout << compliment[i]<<" ";
    return 0;
}