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

⭐️ 난이도

 

Gold 4

 

---

⭐️ 문제

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

14267번: 회사 문화 1

 

 

---

⭐️ Idea flow

 

문제의 요지는 칭찬을 받는 노드의 모든 부하 노드(자식 노드)들에게 칭찬정도를 더하는 것이다.

맨 처음에 생각했던 방법은 input을 통해서 단방향 간선을 연결시키고, 칭찬을 받는 노드와 칭찬 정도를 받을 때 마다 DFS를 실행하여 값들을 구하는 방식이었다.

 

하지만 당연하게도 이 방법으로 풀었더니 시간 초과가 났다.

DFS를 m번(최대 100,000번) 실행하게 되므로 시간초과가 날 수 밖에 없었다.

 

이를 해결하기 위해서는 DFS를 실행하는 횟수를 줄여야 한다. DFS 실행 횟수를 1번으로 줄일 수 있다.

칭찬 받는 노드와 정도를 받을 때마다 DFS를 실행하는 것이 아니라, 해당 정보를 배열에 미리 저장하고 이를 활용한다.

 

몇 번째 노드가 칭찬을 얼마나 받았는지 그 시작점을 우선 배열에 저장한다.

사장(1번 노드)이 트리의 root 노드이기 때문에, DFS를 1번 노드부터 시작해서 여태까지 자신이 받은 칭찬의 양을 모든 자식 노드(자손)들에게 더해준다.

이렇게 하면 DFS를 한 번 실행하면서도 자손들에게 내리 칭찬을 할 수 있다.

 

위의 방법으로 풀다보니 DFS를 m번 실행하는 것과 무슨 차이인지, 시간 복잡도면에서 비슷한게 아닐까하는 생각이 들었다.

맨 처음 풀이(DFS를 m번 실행)는 최대 100,000번 DFS를 하면서 모든 노드의 연결을 확인해야 하지만, 위의 방법(DP)를 사용하면 비슷한 방식이지만 미리 저장되어 있는 정보를 통해서 DFS를 1번만 진행할 수 있다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;

// 14267 - 회사 문화 1
int n, m;
vector<vector<int>> graph;
vector<int> praise;

void input(){
    cin >> n >> m;
    graph.assign(n + 1, vector<int> (0, 0));
    praise.assign(n + 1, 0);

    for(int i = 1; i <= n; i++){
        int superior;
        cin >> superior;
        if(superior != -1)  graph[superior].emplace_back(i);
    }

    for(int i = 0; i < m; i++){
        int person, credit;
        cin >> person >> credit;
        praise[person] += credit;
    }
}

void DFS(int cur){
    for(int i = 0; i < graph[cur].size(); i++){
        int next = graph[cur][i];
        praise[next] += praise[cur];
        DFS(next);
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();

    DFS(1);
    for(int i = 1; i <= n; i++){
        cout << praise[i] << " ";
    }

    return 0;
}