백준 1135 : 뉴스 전하기

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

1135번: 뉴스 전하기

 

tree dp 문제다. 탑다운 방식으로 구현했다.

 

1. 자식 노드로 뉴스를 전하면 그 다음 턴부터 자식 노드에서도 병렬적으로 그 자식노드에게 뉴스를 전하므로, 가장 최소한의 시간으로 목적을 달성하기 위해선 가장 시간이 오래 걸리는 노드부터 소식을 전달해야 한다.

  -> 이 관점에서 보면 그리디 문제이기도 하다.

 

2. 현재 노드에서 모든 자식노드들에 뉴스를 전하는데 걸리는 시간은

(각각의 자식노드가 자신의 모든 자식노드들에 뉴스를 전달하는 시간) + (현재 노드에서 해당 노드에 뉴스를 전달한 순서 i) 중 가장 큰 값이다.

예를 들면, 현재 노드의 자식노드가 3개 있고 각각의 자식노드가 자신의 자식노드들에게 뉴스를 전달하는데 걸리는 시간이 각각

 

0번 째 자식 노드 -> 3분,

1번 째 자식 노드 -> 3분,

2번 째 자식 노드 -> 4분 이라면,

1번 로직에 의해 2번째 자식노드, 0번째 자식노드, 1번째 자식노드 순으로 소식을 전달해야 하고 각각의 자식노드들에 소식을 전달하는데 1분이 소요되므로 각각의 자식노드들이 뉴스를 전하는 시간은 

 

2번 째 자식 노드 -> 4분 + 1분 = 5분,

0번 째 자식 노드 -> 3분 + 2분 = 5분,

1번 째 자식 노드 -> 3분 + 3분 = 6분 이 되므로, 해당 노드에서 모든 자식노드들에 뉴스를 전하는 최소 시간은 세 개의 자식 노드들 중 가장 오랜 시간이 걸리는 6분이 된다.

 

3. 현재 노드의 자식노드를 루트 노드로 하는 서브트리도 1, 2번 로직과 같은 방법으로 최소 시간을 계산할 수 있다.

  -> 어떠한 큰 문제를 작은 문제들로 나누어 해결할 수 있다. -> DP로 해결할 수 있다.

 

4. 한 번 계산한 노드에서 중복하여 계산하지 않도록 메모이제이션을 사용한다.

 

코드로 구현하면 아래와 같다.

 

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

using namespace std;

int n;
vector<int> child[50];
int tree_dp[50];

int DP(int cur) {
	// 메모이제이션 되어있을 경우 해당 값 리턴
	if (tree_dp[cur] != - 1) return tree_dp[cur];
	// 자식 노드가 없다면(리프노드라면) 걸리는 시간이 없으므로 0을 메모이제이션하고 리턴
	if (!child[cur].size()) return tree_dp[cur] = 0;

	// 현재 노드의 각각의 자식 노드들이 자신의 자식 노드들에 뉴스를 전파하는데 걸리는 시간을 담을 벡터 변수
	vector<int> cur_child_cost;

	// 탑다운 재귀 방식으로 자식 노드들의 최소 시간을 계산, 리턴받아 cur_child_cost에 저장
	for (int i = 0; i < child[cur].size(); i++) {
		cur_child_cost.push_back(DP(child[cur][i]));
	}

	// 가장 오랜 시간이 걸리는 자식 노드부터 뉴스를 전달하기 위하여 내림차순 sort 수행
	sort(cur_child_cost.begin(), cur_child_cost.end(), greater<>());
	// 뉴스를 전하는 순서에 따라 추가적으로 소요되는 시간 더해줌
	for (int i = 0; i < cur_child_cost.size(); i++) {
		cur_child_cost[i] += i + 1;
	}

	// 현재 노드의 자식노드들 중에서 가장 오래 걸리는 시간이 최소 시간이므로 메모이제이션 하고 리턴
	return tree_dp[cur] = *max_element(cur_child_cost.begin(), cur_child_cost.end());
}

void solution() {
	int tmp;
	cin >> n;
	cin >> tmp;
	for (int i = 1; i < n; i++)
		cin >> tmp, child[tmp].push_back(i);

	for (int i = 0; i < n; i++)
		tree_dp[i] = -1;

	cout << DP(0);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2024 kb

시간: 0 ms