BOJ 14267번: 회사 문화 1

문제 설명

부하들에게 연쇄적으로 칭찬이 전달될 때, 각 부하가 받은 칭찬 수 구하기

🔗 문제 링크

핵심 아이디어

• 트리 배열, 칭찬 배열, 정답 배열 3개의 자료 구조로 해결하기
• DFS에서 다음 부하로 칭찬 누적할 때 (칭찬 배열 속 칭찬 + 여태껏 누적된 칭찬) 으로 넣기
• 사장은 상사가 없으니 계산에서 제외하기

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, a, u, w;
vector<int> adj[100005];
int good[100005];
int ans[100005];

void dfs(int cur, int total){
    ans[cur] = total + good[cur];
    for(int nxt : adj[cur]){
        dfs(nxt, ans[cur]);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a;
        if (i == 1) continue;
        adj[a].push_back(i);
    }
    
    for(int i = 0; i < m; i++){
        cin >> u >> w;
        good[u] += w;
    }
    
    dfs(1,0);
    
    for(int i = 1; i <= n; i++){
        cout << ans[i] << ' ';
    }
}

‼️ 주의할 점

• 칭찬 배열 입력 받을 때 덮어쓰지 않도록 주의하기
• 무조건 트리 형태이니 vis 배열로 부모인지 확인할 필요 없음 & 양방향 그래프 안 만들어도 됨
• 상사 안에 부하를 넣어서 연쇄적으로 부하들을 타고 내려가면서 값 계산 잘 할 수 있게 하기!
• 값이 섞이기 쉬우니 칭찬 배열을 정답 배열로도 활용하지 말기!