문제 푼 날짜 : 2021-10-01

문제

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

접근 및 풀이

그다지 어렵지 않은 DFS 문제였던 것 같다.
입력을 받으면서 칭찬 받은 사람들은 각각 칭찬받은 정도를 저장해둔다.
모든 입력을 받은 후, 1번 노드(사장)부터 DFS를 통해 본인이 받은 칭찬들을 아래 사람들에게 더해준다.

코드

// 백준 14267번 : 회사 문화 1
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> org[100001];
int dp[100001];

void dfs(int node) {
    for (int i = 0; i < org[node].size(); i++) {
        int next = org[node][i];
        dp[next] += dp[node];
        dfs(next);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    int r;
    for (int i = 0; i < n; i++) {
        int root;
        cin >> root;
        org[root].push_back(i + 1);
    }
    
    for (int i = 0; i < m; i++) {
        int node, score;
        cin >> node >> score;
        dp[node] += score;
    }
    dfs(1);
    
    for (int i = 0; i < n; i++) {
        cout << dp[i + 1] << ' ';
    }
    
    return 0;
}

결과

피드백

DFS는 풀 때마다 난이도가 어떻든간에 쫄고 들어가서 잘 못푸는것 같다...
연습을 더 하는 수밖에...