백준 1135 - 뉴스 전하기

문제 설명

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

오민식의 사원 번호는 0이고, 다른 사원의 번호는 1부터 시작한다.

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

 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 트리의 루트부터 시작하여 모든 노드를 한 번에 하나씩 방문할 때 최소비용을 구하는 것이다.

한 번에 하나씩이라는 말의 의미는 뉴스를 들은 노드는 자식 노드에게 뉴스를 전달할 수 있는데 1분에 하나의 노드에게만 전달할 수 있다는 뜻이다.

즉, 자식 노드를 적절한 순서로 골라 뉴스를 전달해야 한다.

 

문제의 핵심은 자식 노드를 고르는 순서이다.

자식 노드를 고르는 기준은 간단하다.

depth가 가장 긴 노드부터 고르면 된다.

depth는 1분에 1씩 증가할 수 밖에 없다.

따라서, depth가 가장 긴 노드에게 먼저 전달해야 최소한의 시간이 걸린다.

이때, 한 가지 주의할 점은 하나의 노드를 선택했다면 다음 노드는 1분 이후에 전달할 수 있다는 뜻이다.

 

예를 들어 보자.

2번 노드는 4, 5, 6, 9번 노드에게 뉴스를 전달할 수 있다.

하지만, 자식 노드들은 모두 리프 노드이다.

따라서, depth로 구분할 수 없기 때문에 아무거나 선택해도 된다.

노드 번호가 빠른 순으로 전달했다고 해보자.

4번 노드에게 뉴스를 전달하며 다음 노드인 5번 노드에게 뉴스를 전달할 수 없다.

따라서, 2번 노드에서는 적어도 자식 노드의 개수만큼은 시간이 들 것이다.

 

정리하자면, 2번 노드의 최종적인 전달 시간은 자식노드의 최대 depth를 기준으로 선택하되 지나간 시간을 고려하여 보정해 주어야 한다.

즉, depth를 기준으로 정렬(내림차순)한 뒤 1분씩 더 걸린 시간을 보정하여 계산해야 한다.

sort(SubTree.begin(), SubTree.end(), greater());

int ret = 0;
for (int i = 0; i < SubTree.size(); i++)
{
    ret = max(ret, SubTree[i] + (i + 1));
}

 

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <set>

using namespace std;

int N;

int DFS(vector<vector<int>>& Tree, int current) {
    if (Tree[current].empty()) return 0;

    vector<int> SubTree;
    for (int i = 0; i < Tree[current].size(); ++i)
    {
        SubTree.push_back(DFS(Tree, Tree[current][i]));
    }

    sort(SubTree.begin(), SubTree.end(), greater());

    int ret = 0;
    for (int i = 0; i < SubTree.size(); i++)
    {
        ret = max(ret, SubTree[i] + (i + 1));
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    vector<vector<int>> Tree(N);
    for (int i = 0; i < N; i++)
    {
        int parent;
        cin >> parent;
        if (parent == -1) continue;

        Tree[parent].push_back(i);
    }

    cout << DFS(Tree, 0);

	return 0;
}

---