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

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

14267번: 회사 문화 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
vector<int>v[100001];
int cost[100001];

void dfs(int cur)
{
    for(int i=0; i<v[cur].size(); i++)
    {
        int next = v[cur][i]; //cur에 대한 직원
        cost[next] += cost[cur]; //내리칭찬 저장
        dfs(next);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;
    for(int i=1; i<=N; i++)
    {
        int n;
        cin >> n;
        v[n].push_back(i); //해당 직속 상사에 대한 직원 저장
    }

    for(int i=1; i<=M; i++)
    {
        int a, b;
        cin >> a >> b;
        cost[a]+=b; //입력받은 칭찬 저장
    }
    dfs(1);
    
    for(int i=1; i<=N; i++) cout << cost[i] << " ";
    return 0;
}

 

dfs를 사용하여 풀 수 있는 문제이다.

먼저 직속 상사를 입력받을 때, 해당 직속 상사에 대한 직원을 직속 상사에 연결하여 저장해준다.

 

이후 칭찬받을 대상과 칭찬의 수치가 주어지는데, 이때 바로 해당 대상에게 받은 칭찬의 수치를 저장해준다.

이후 사장의 값인 1부터 dfs 탐색을 시작한다.

 

사장과 연결된 부하들을 탐색하여 해당 부하의 값에 현재 값 (칭찬 수치)를 더해준다.

이를 반복하며 직속 상사와 연결된 부하들의 내리칭찬 (칭찬 수치 더해주기)를 반복해준다.

 

이후 각 직원에 따라 저장된 칭찬수치의 값을 출력해주면 된다.