[BOJ 1135 // C++] 뉴스 전하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1135번 문제인 뉴스 전하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1135

1135번: 뉴스 전하기

이 문제에서 가장 까다로운 부분은 한 사람의 직접적인 부하들에게 연락을 걸 때 어떤 순서로 해야하는지 결정하는 부분인 것 같다.

 

어떤 직원이 직접 연락을 해야 하는 부하들 N명이 있다면, 이 부하중 연락하는데 가장 오래걸리는 사람서부터 먼저 전화를 걸어, 시간이 가장 오래걸릴 사람을 찾아야한다. 예를 들어, 어떤 사람의 부하가 5명이고, 각 부하의 직간접적인 부하들이 모든 연락전달을 받는 데에 걸리는 시간이 5, 2, 2, 2, 2분이라 하자. 이 때, 시간이 가장 오래 걸리는 부하에게 먼저 전화를 걸면 각 부하들이 모든 직간접적인 부하들에게 전달하는 데에 걸리는 시간은 각각 5, 3, 4, 5, 6분이 되므로 이 직원이 직간접적 부하들에게 내용을 전달하는 시간은 6분이 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using std::cin; using std::cout;
using std::vector;
using std::sort;
using std::max;

vector<int> G[51];

int dfs(int root, int parent) {
    vector<int> stk; // 직접 연락해야하는 각 부하들이 직간접적 부하들에게 내용을 전달하는 최소시간들
    vector<int>::iterator iter = G[root].begin();
    for (iter;iter != G[root].end();iter++) {
        if (*iter == parent) continue;
        stk.push_back(dfs(*iter, root));
    }
    if (stk.empty()) return 0;
    else {
        sort(stk.begin(), stk.end()); //정렬
        int ret = 0;
        iter = stk.begin();
        for (int i = stk.size() - 1;i >= 0;i--) {
            if (*iter + i > ret) ret = *iter + i;
            iter++;
        }
        return ret + 1;
    }
}

int main()
{
    int N; cin >> N;
    int dump; cin >> dump;
    for (int i = 1;i < N;i++) {
        int temp; cin >> temp;
        G[i].push_back(temp);
        G[temp].push_back(i);
    }
    cout << dfs(0, 0);
    return 0;
}