[BOJ 1135] 뉴스 전하기

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

1135번: 뉴스 전하기

 

- 문제 요약

 

민식이는 회사의 매니저이다.

그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다.

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

자기 자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다.

뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다.

이 것은 모든 직원이 뉴스를 들을 때까지 계속된다.

모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다.

이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

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

 

 

- 알고리즘 정리

 

문제에서 전화는 정확하게 1분 걸리고, 한 번에 한 사람씩 전화를 한다고 했습니다.

이는 0번째 직속 부하에게 전화를 걸면 그다음 직속 부하는 전화를 받을 때까지 1분을 대기한다는 뜻입니다.

그러므로 대기 시간을 최소화 하려면 전파하는데 가장 오래 걸리는 부하 직원에게 먼저 전화를 걸어야 모든 직원이 소식을 듣는 데 걸리는 시간의 최솟값을 구할 수 있습니다.

=> 현재 노드를 기준으로 자식 노드가 있다면 전파 소요 시간에 따라 그리디하게 전화를 걸어주고, 자식 노드가 없다면 1을 리턴해주면 됩니다. (DFS)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int n,a;
vector<vector<int>>vv;

int dfs(int x){
	vector<int>v;
	int ret=0;
	int Size=vv[x].size()-1;
	for(auto i:vv[x]){
		v.push_back(dfs(i));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		ret=max(ret,v[i]+Size);
		Size--;
	}
	return ret+1;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	vv.resize(n);
	for(int i=0;i<n;i++){
		cin>>a;
		if(a==-1){
			continue;
		}
		vv[a].push_back(i);
	}
	cout<<dfs(0)-1;
}

코드 제출 결과