[Algorithm] Baekjoon 1135번 : 뉴스 전하기

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
int n;
vector<vector<int>> graph(51);
 
 
int DFS(int node)
{
    vector<int> v;
    int result = 0;
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int child = graph[node][i];
 
        v.push_back(DFS(child));
    }
 
    sort(v.rbegin(), v.rend());
 
    for (int i = 0; i < v.size(); ++i)
    {
        result = max(result, v[i] + i+1);
    }
 
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        int num;
        cin >> num;
 
        if (i == 0) continue;
 
        graph[num].push_back(i);
    }
 
 
    cout << DFS(0);
}
 
 
 

 

 

자식들에게 전파할 때 1분씩 추가될 때, 전부 퍼뜨리는데에 필요한 최소값을 구하는 문제이다.

자식이 여럿 있을 때, 퍼뜨리는데에 가장 오래걸리는 자식한테 먼저 퍼뜨리는게 무조건적으로 유리하다.

그렇다고 가장오래걸리는 자식이 쭉쭉 퍼지는 동안, 나머지 자식들이 전부 퍼진다는 보장이 없기때문에

40번째 라인처럼 최대값을 전부 비교해줘야 한다.