[C++] 14267번 회사 문화 1

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

---

 

25/04/11

 

 

간단한 트리 문제다. 여러 방면으로 풀 수 있는 좋은 문제인 것 같아서 소개한다.

---

 

문제 접근 방식:

 

 

먼저 문제에서 요구하는 것을 한줄로 살펴보자.

 

각 노드의 값은 상위 노드에 있었던 값(정확히 말하면 직속 상사가 해당 노드(부하)에게 주었던 칭찬)들의 누적 합이다.

 

이를 여러 가지 방안으로 구현할 수 있는데, 기본적으로 누적합이기 때문에 DP라고 볼 수 있다.

 

근데 트리다. 따라서 넓게 보면 트리 DP다!

 

이를 구현하는 방안은 1. BFS, 2. DFS, 3. 기타 등등 DFS의 변형

 

근데 나는 BFS가 가장 먼저 떠올라서 BFS로 했다.

 

BFS로 루트부터 탐색 시작해서, 노드랑 현재까지의 값(근데 이건 DP 배열에 잘 저장되어있다.)을 들고 가면서 DP배열에 채워 넣어준다.

 

만약 부하가 받은 칭찬이 있다면 더해주면 된다. 근데 그건 아래 코드를 보면 알 수 있지만, chingchan배열을 선언하고, chingchan[i] = i번 부하가 받은 칭찬으로 정의했기 때문에 이를 활용한다.

 

DFS로도 가능하고, 이게 아마 시리즈 문제라서 오일러 투어 테크닉 등 다양한 풀이 방법으로 푼 사람이 존재했다.

 

근데 나는 ETT를 안배웠기 때문에 패스.   

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 14267번 회사 문화 1
// BFS
/*
접근 방법:
DP[i] = i번 직원이 받은 칭찬의 정도
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

void topDown(const vector<vector<int>>& graph, vector<int>& DP, const vector<int>& chingchan, int start){
    queue<pair<int, int>> Q;
    DP[start] = 0;
    Q.push({start, 0});
    while (!Q.empty()){
        int now = Q.front().first;
        int value = Q.front().second;
        Q.pop();
        for (auto near: graph[now]){
            if (DP[near] == -1){
                DP[near] = value + chingchan[near];
                Q.push({near, DP[near]});
            }
        }
    }
    return;
}

int main(void){
    fastio;
    int N, M; cin >> N >> M;
    vector<vector<int>> graph(N);
    int parent;
    for (int child = 0; child < N; child++){
        cin >> parent;
        if (parent == -1){
            continue;
        }
        graph[parent-1].push_back(child);
    }
    vector<int> DP(N, -1);
    vector<int> chingchan(N, 0);
    int num, CC;
    for (int i = 0; i < M; i++){
        cin >> num >> CC;
        chingchan[num-1] += CC;
    }
    topDown(graph, DP, chingchan, 0);
    for (int i = 0; i < N; i++){
        cout << DP[i] << ' ';
    }
    return 0;
}