백준 1135 뉴스전하기 C++

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

1135번: 뉴스 전하기

뭔가 dp를 적용하면 될 거 같은 문제였지만 아이디어를 생각해내는데 좀 시간이 걸렸습니다. (뭔가 비슷한 문제 전에 푼 거 같기도..??)

 

자식 노드 1명에게만 전화할 수 있으므로, 각 자식 노드가 자식 노드가 루트인 서브트리로 전파하는데 걸리는 시간을 알고있다고 가정하면, 그 결과의 내림차순으로 1씩 더해준 결과의 최댓값이 결국 해당 노드가 루트인 서브트리의 결과입니다.

 

예를 들어 맨 마지막 리프노드를 갖는 트리를 생각하면 (서브트리 루트 A, 리프노드 a,b라 가정)

리프노드 a,b 는 더 이상 전파할 것이 없으므로 결과는 0입니다. 그리고 A는 a,b에게 전파하기 위해 a, b 순으로 전달한다고 하면 a는 1분, b는 2분이 걸립니다. (1 = 0 + 0 + 1, 2 = 0 + 1 + 1)

이를 모든 서브트리에 적용한다면, 자식 노드 결과 + 내림차순 인덱스 + 1 의 최댓값을 반복해서 구하면됨을 알 수 있습니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> vec[51]; // vec[i] : i가 부모인 자식 노드들

void init()
{
	cin >> n;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num == -1)
			continue;
		vec[num].push_back(i);
	}
}

int dfs(int node, int parent)
{
	int ret = 0;

	vector<int>result; 
	// 각 자식 노드가 루트가 되는 서브트리의 결과 

	for (auto child : vec[node]) {
		int child_ret = dfs(child, node);
		result.push_back(child_ret);
	}

	// 결과 큰 애부터 먼저 전파시켜야함
	sort(result.rbegin(), result.rend());

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

	return ret;
}

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

	init();
	
	cout << dfs(0, -1);
}