boj, 백준) 1135. 뉴스전하기 (C/C++)

1. 문제 링크

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

2. 문제 개요

회사는 트리구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

 

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이것은 모든 직원이 뉴스를 들을 때까지 계속된다.

 

모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸린느 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

 

3. 문제 힌트

루트(민식)의 자식들이 루트인 서브트리를 생각해보자. 자신의 자식들이 모두 전파하는데 걸리는 시간은 얼마인지 생각해보자.

이거는 DFS탐색으로 구할 수 있다. 

단, 동시에 전파할 수 있기 때문에, DFS 재귀가 끝날 때 '어떤' 처리를 해주어야 한다.

 

 

그리고, 한 번에 한 명에게만 전파할 수 있다.

이거를 어떻게 구현할 수 있을까.. 생각해보자

 

4. 문제 풀이

(3)에서 말씀드린 것처럼,

루트 입장에서 보자, 자신의 각 자식들에게 '너는 모두 전파하는데 몇 분 걸리니?'라는 함수를 실행했다고 하자.

그러면 함수를 실행하고 각 자식들은 return값을 가져올 텐데,

이거는 순차적인 것을 반영하지 않은 결과이다.

 

왜냐하면 문제에서 1번에 1명에게만 할 수 있다고 했기 때문.

그래서 어떤 결괏값이 1, 2, 3, 4, 5분 나왔다고 했을 때, 모두 전파하는데 5분 걸리는 자식에게 가장 먼저 전파해야(Greedy) 최소의 시간이 걸릴 것이다.

5분 + 0분(첫 번째 전파) , 4분 + 1분(두 번째 전파)..... 1분 + 4분(5번째 전파)

->위의 값 중 최댓값을 택한다. 이로써 각 한 명에게 전파할 수 있다는 부분을 만족시켜 주었다.

 

자, 이제는 어떻게 저 1, 2, 3, 4, 5분을 구할 수 있느냐이다. 그 함수를 작성해야 한다.

트리이기 때문에 분할 정복으로 문제를 작게 쪼갤 수 있다.

 

리프 노드인 경우를 생각해보자.

전파하는데 당연히 0분이 걸릴 것이다.

그럼 문제의 예제와 같은

 

예를 보면,

각 자식에게 전파하는데 1분, 1분이 걸린다.

위의 예처럼 순서대로 전파하는 것을 고려한다면 답은 2,

위의 예에서 0번 노드 위에 부모가 있다고 하면 

이렇게 2라는 값을 반환시켜준다.

그럼 부모 노드 입장에서는 2를 가지고 똑같은 연산을 반복해주기만 하면 된다.

 

-> 이처럼 리프 노드라면 자기 자신에게 전파되는 시간 1분을 반환시켜주고, 자식 노드가 존재하는 노드는 자식 노드들의 정보를 모두 정렬하고, 위의 Greedy 한 방식으로 최대 시간을 구해낸다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> adj;
int n;

int dfs(int cur)
{
	vector<int> v;
	int ret = 0;
	int w = adj[cur].size() - 1;

	for (int next : adj[cur])
		v.push_back(dfs(next));
	
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); ++i)
		ret = max(ret, v[i] + w--);
		
	return ret + 1;
}

int main()
{
	scanf("%d", &n);
	adj.resize(n);

	for (int i = 0; i < n; ++i) {
		int p;
		scanf("%d", &p);

		if (p == -1)
			continue;

		adj[p].push_back(i);
	}
	int ans = dfs(0);

	printf("%d", ans - 1);

	return 0;
}

 

 

6. 결과