99클럽 코테 스터디 12일차 TIL, 백준 / 뉴스 전하기

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

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <thread>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <math.h>
#include <stack>
#include <algorithm>
#include <unordered_map>

#define endl "\n"
#define INT_MAX int(1e9)
#define MAX 10001

using namespace std;
/*
     0               0
   1  2             2 (자식 개수)
      3 4           3(자기 제외 같은 트리내 다른 애들 개수 ?)

     0  5
    1   4
    2   3
    3   2
    4   1

                                0                                               // 0
                1                                 2                            // 2
    3         4           5               6           7                      // 4
  8  9    10 11    12   13      14        15      16                // 6 ?
  17                  18    19     20                21 22 23
*/

int N;
vector<int> minTime;
unordered_map<int, vector<int>> tree;

// 1) 자기의 자식 노드들까지 가장 전파하는 데 가장 오래 걸리는 녀석부터 전파해야 한다. (Greedy)
// 2) 그러면 각 노드들에게, 너를 포함해서, 노드들까지 다 전파하는데 얼마나 걸려 ? 를 계산해야 한다.
//     이때, 리프 노드라면 걸리는 시간 1. 아니라면 자식 노드들 중 뉴스 전파하는데 걸리는 총 시간 높은 순부터 전파.
// 3) 그리고, 가장 많은 녀석을 선택해가는 과정이라고 생각하면 된다.
int dfs(int n)
{
    // 자식 노드들 각각 총 전파시간 모아서 정렬하기 위함
    vector<int> v;

    int ret = 0;
    int w = tree[n].size() - 1;

    for (int child : tree[n])
    {
		v.push_back(dfs(child));
	}

    sort(v.begin(), v.end(), greater<int>());   // 내림차순 정렬

    for (int i = 0; i < v.size(); i++)
    {
        ret = max(ret, v[i] + i);   
        // i 를 더하는 이유 ? ex) 1번째 idx 에 전파할 때는, 앞에 0 번째 노드에 전파하고 나서 + 1 이 
        // 더 걸리기 때문이다.
    }

    return ret + 1; // 자기 자신에게 전파시간 + 1 (리프 노드는 1 리턴)
}

void Input()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
		int a;
		cin >> a;
		tree[a].push_back(i);
	}
};

void Solve()
{
    	cout << dfs(0) - 1 << endl;
}

int main() {
    ios::sync_with_stdio(false);

    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input_c.txt", "r", stdin);

    Input();

    Solve();
    
    return 0;
}