백준 1135번 - 뉴스 전하기

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

1135번: 뉴스 전하기

 

문제 요약

 

- 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다.
- 모든 직원은 민식이의 직접 또는 간접적인 부하이다. (루트 = 민식)
- 1분에 한 사람씩에게만 뉴스를 전파할 수 있음

- 모든 직원이 뉴스를 접하게 되는 최소 시간을 구하라

 

해결

 

처음에는 자식 노드가 많은 직원부터 소식을 전파하면 되지 않을까 생각해봤는데 조금만 더 고민해보면 당연히 그렇지 않다는 것을 알 수 있었다.

 

간단하게 아래의 예시를 통해 살펴보면 된다

 

1번 노드는 모든 자식 노드가 6개이다.

2번 노드는 모든 자식 노드가 5개이다.

 

하지만 1번 노드가 모든 자식 노드들에게 뉴스를 전파하는 시간은 총 4분이고

2번 노드가 모든 자식 노드들에게 뉴스를 전파하는 시간은 총 5분이다.

 

즉 자식 노드가 많다고 반드시 오래 걸리는 것이 아니다.

 

그럼 어떤 방식으로 비교해야 할까?

 

정말 단순하게 생각해보면 자신의 자식 노드들에게 뉴스를 전파하는데 걸리는 총 시간으로 비교하면 된다.

나는 이 부분에서 Bottom-up 방식으로 자식 노드들이 걸리는 시간들을 채워놓고 현재 노드가 걸리는 시간을 계산하면 될 것 같다고 생각했다.

 

int solve(int node) {
	// 리프노드라면
	if (tree[node].empty()) {
		return 1;
	}
	// 리프노드가 아니라면
	// 자식 노드의 cost 배열에서 각 index를 + 해주고 그 중 max 값이 걸리는 시간임 = 즉 해당 노드의 cost
	// 해당 노드의 cost 값을 구하려면 자식 노드들의 값이 전부 구해져 있어야 한다.
	vector<int>child;
	for (int i = 0; i < tree[node].size(); i++) {
		child.push_back(solve(tree[node][i]) + 1); // 해당 노드도 전파 횟수에 추가되어야 함, 즉 + 1
	}
	sort(child.begin(), child.end(), greater<int>());
	int ret = 0;
	for (int i = 0; i < child.size(); i++) {
		ret = max(ret, child[i] + i);
	}
	return ret;
}

 

위의 코드를 보자.

 

만약 리프 노드라면 반드시 걸리는 시간은 1분 일 것이다.

 

리프 노드가 아니라면 자식 노드들 중 뉴스를 전파하는데 걸리는 총 시간(cost)이 높은 순부터 전파하면 된다.

 

이때 약간의 함정들이 존재한다.

 

먼저 자식 노드들에게 뉴스를 전파하는데 걸리는 총 시간에 + 1을 해주어야 한다.

이유는 자기 자신도 전체적인 트리의 입장에서 보면 결국 전파를 받아야 하는 입장인 것이다.

하지만 루트 노드는 이미 전파되어 있는 상태이기 때문에(문제의 조건) 마지막에 출력해 줄 때 1을 빼주어야 한다.

 

다음으로 아래의 코드 부분이다.

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

 

내 개인적으론 이 부분이 가장 떠올리기 힘들었고 떠올리고 나서는 이마를 탁 쳤던 부분이다.

 

child 배열에는 어떠한 노드의 자식 노드들의 모든 cost값이 내림차순으로 정렬되어 들어있다. (재귀 함수를 통해 구한 값들이다)

 

이때 왜 가장 cost가 큰 노드만을 사용하는 게 아니라 max를 취하는지 잘 생각해봐야 한다.

 

child 배열이 다음과 같다고 생각해보자.

int child [] = { 4, 3, 3, 2, 1 }

 

이제 해당 노드의 cost를 구해보자.

현재 해당 노드의 cost 값은 0이다.

 

문제의 조건에서 1분에 한 명씩에게만 전파할 수 있다고 하였으므로 4의 cost를 지니는 자식에게 먼저 전파할 것이다.

즉 cost 5의 자식 노드를 모두 전파시키는 데에는 총 0 + 4 = 4분이 걸릴 것임을 알 수 있다.

 

이제 다음 자식 노드에게 뉴스를 전파한다.

이때는 현재 노드를 기준으로 보면 1분이 지난 시점이기 때문에 (첫 번째 자식 노드에게 전파했기 때문)

cost 3의 자식 노드를 모두 전파시키는 데에는 총 1 + 3 = 4분이 걸릴 것이다.

 

여기서 중요하다.

다음 자식 노드 역시 현재 노드를 기준으로 보면 2분이 지난 시점이다.

그렇다면 cost 3의 자식 노드를 모두 전파시키는데에는 총 2 + 3 = 5분이 걸릴 것이다.

 

분명 첫 번째 자식 노드의 cost 값은 5였고 세 번째 자식 노드의 cost 값은 3이었는데 걸리는 시간은 세 번째 자식 노드가 더 크다.

 

이러한 부분 때문에 반드시 max 값으로 설정해 주어야 하는 것이다.

 

 

Bottom-up 방식으로 구하는 것은 재귀를 공부하며 많이 다뤄봤을 것이므로 어렵지 않게 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n;
vector<int>tree[55];

int solve(int node) {
	// 리프노드라면
	if (tree[node].empty()) {
		return 1;
	}
	// 리프노드가 아니라면
	// 자식 노드의 cost 배열에서 각 index를 + 해주고 그 중 max 값이 걸리는 시간임 = 즉 해당 노드의 cost
	// 해당 노드의 cost 값을 구하려면 자식 노드들의 값이 전부 구해져 있어야 한다.
	vector<int>child;
	for (int i = 0; i < tree[node].size(); i++) {
		child.push_back(solve(tree[node][i]) + 1); // 해당 노드도 전파 횟수에 추가되어야 함, 즉 + 1
	}
	sort(child.begin(), child.end(), greater<int>());
	int ret = 0;
	for (int i = 0; i < child.size(); i++) {
		ret = max(ret, child[i] + i);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		if (i == 0) continue; 
		tree[v[i]].push_back(i); // 자식 노드들을 가지고 있음
	}
	// -1 하는 이유는 root 노드는 제외
	cout << solve(0) - 1 << "\n";
}

 

사실상 주석을 빼면 몇 줄 되지 않는다.

다른 사람들도 이렇게 구했는지는 잘 모르겠는데 한 번에 맞춰서 생각보다 놀랐다..

이 문제가 Tree DP 문제라는데 재귀식으로 dp를 잘 안 풀어 봐서 크게 느껴지진 않았다.