[백준] 1135 뉴스 전하기

문제 링크 : www.acmicpc.net/problem/1135

1135번: 뉴스 전하기

[문제 유형]

Tree DP, Greedy

 

만약 한 사원에 대해, 그 사원의 직속 부하(즉, 인접 자식 노드)로부터 전파가 완료되는 시간을 모두 알고 있다고 가정해보자.

이 때, 전파 시간이 오래 걸리는 사원에게 먼저 전파하는 것이 총 전파 시간을 줄이는 데 반드시 좋을 것이다. 직속 부하에게는 한 번에 한 명에게만 전파가 가능하기 때문이다.

따라서 각 직속 부하들로부터 완료되는 전파 시간들을 큰 순으로 정렬하고, 이들의 순서만큼 직속 부하에게 직접 전파하는 시간(첫 번째로 전달하는 직속 부하라면 1분, 두 번째라면 2분 ...)을 더해 최댓값을 구한다.

이 최댓값이 곧 현재 사원에서 전파하여 그 사원을 root로 하는 서브트리 전체에 전파하기까지의 최소 시간이 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <memory.h>
 
#define INF 1000000007
 
using namespace std;
typedef pair<int, int> p;
typedef long long ll;
 
int n;
vector<int> adj[51];
 
bool cmp(int a, int b) {
    return a > b;
}
 
int get_time(int node, int pnode) {
    int ret = 0;
    vector<int> res;
    for (int i = 0; i < adj[node].size(); i++) {
        int child = adj[node][i];
        res.push_back(get_time(child, node));
    }
 
    sort(res.begin(), res.end(), cmp);
    for (int i = 0; i < res.size(); i++) {
        ret = max(ret, res[i] + i + 1);
    }
    //printf("ret value at %d is %d\n", node, ret);
 
    return ret;
}
 
void init() {
    int parent;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> parent;
        if (parent == -1) continue;
        adj[parent].push_back(i);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    int answer = get_time(0, -1);
    printf("%d\n", answer);
 
    //system("PAUSE");
    return 0;
}