백준 1135 뉴스 전하기 (c++) : 피너클

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

1135번: 뉴스 전하기

트리, 그리드 문제다.

 

cin >> n;
cin >> a;
for (int i = 1; i < n; i++) {
	cin >> a;
	v[a].push_back(i);
}
cout << dfs(0) << endl;

입력받은 다음 dfs돌려 풀면 된다.

맨 처음 입력되는 -1을 무시하기 위해 n을 입력받은 다음 바로 a하나를 입력받았다.

int dfs(int now) {
	if (v[now].size() == 0) return 0;

dfs는 현재 직원 전달받는다.

만약 현재 직원의 부하 수가 0이라면 바로 0을 리턴한다. 전달할 사람이 없으니 0분이 걸린다.

dfs는 현재 직원아래 간접 부하 모두에게 정보를 전달하는데 걸리는 최대 시간을 리턴한다.

	int ans = 0;
	vector<int> reaf;
	for (int i = 0; i < v[now].size(); i++) reaf.push_back(dfs(v[now][i]));
	sort(reaf.begin(), reaf.end(), greater<>());

vector<int> reaf에는 직원 부하가 부하의 부하들에게 전화를 돌리는데 걸리는 최대 시간을 저장한다.

그후 시간이 높은 순서대로 정렬한다.

	for (int i = 0; i < v[now].size(); i++) {
		ans = max(ans, reaf[i] + i + 1);
	}
	return  ans;
}

마지막으로 하나하나 돌리며 reaf[i] + i + 1값들중 최대값을 리턴한다.

i + 1을 하는 이유는 현재 직원이 부하직원에게 전화를 한번한번씩 돌리기 때문이다.

3명의 부하직원이 있다고 하면 

첫번째 부하직원에게 전화를 돌리고 (1분)

두번째 부하직원에게 전화를 돌리고 (2분)

세번째 부하직원에게 전화를 돌리게 되기 때문이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

int n, a;
vector<int> v[51];

int dfs(int now) {
	if (v[now].size() == 0) return 0;

	int ans = 0;
	vector<int> reaf;
	for (int i = 0; i < v[now].size(); i++) reaf.push_back(dfs(v[now][i]));
	sort(reaf.begin(), reaf.end(), greater<>());

	for (int i = 0; i < v[now].size(); i++) {
		ans = max(ans, reaf[i] + i + 1);
	}
	return  ans;
}

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

	cin >> n;
	cin >> a;
	for (int i = 1; i < n; i++) {
		cin >> a;
		v[a].push_back(i);
	}
	cout << dfs(0) << endl;
}

전체코드다.