[1135번] 뉴스 전하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

이 문제는 해당하는 상사가 부하에게 전화할 때 가장 오래 걸리는 순으로 정렬한 후 전화를 걸어주면 문제를 해결 할 수 있게 된다.

23 

-1 0 1 1 1 2 2 2 3 3 3 4 4 4 0 14 15 16 17 18 19 20 21

이 예제 케이스를 직접 손으로 그려서 확인해본다면 좀 더 쉽게 알 수 있다.

나머지 내용은 주석을 통해 달아두었다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <iostream> #include <cstdio> #include <vector> #include <algorithm>   using namespace std;   typedef pair<int, int> pii;   vector<pii> vc[52];   bool comp(const pii &a, const pii &b) {     return a.first > b.first; }   int dfs(int here) {     int ret = 0;       // 현재 사람이 부하에게 전화하는데 걸리는 시간     for (int i = 0; i < vc[here].size(); i++)     {         int next = vc[here][i].second;         vc[here][i].first = 1 + dfs(next);     }       // 부하에게 전화하는데 가장 오래 걸리는 순으로 정렬     sort(vc[here].begin(), vc[here].end(), comp);       // 정렬된 순서대로 전화할때     for (int i = 0; i < vc[here].size(); i++)     {         vc[here][i].first += i;         ret = max(ret, vc[here][i].first);     }       return ret; }   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);           if (val == -1)             continue;           vc[val].push_back({ 0,i });     }       printf("%d", dfs(0));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus