[BOJ/백준 1135/C++] 뉴스 전하기

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

1135번: 뉴스 전하기

 

[문제 요약]

- 민식이의 회사는 트리 구조이다.

- 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

 

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

뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다.

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

 

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

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

 

[문제 조건]

- 첫째 줄에 직원의 수 N이 주어진다.

- 둘째 줄에는 0번 직원부터 그들의 상사의 번호가 주어진다. 0번 직원 (오민식)은 상사가 없기 때문에 -1이고, 나머지 직원 i의 상사 번호는 i보다 작거나 같은 음이 아닌 정수이다.

- N은 50보다 작거나 같은 자연수이다.

- 시간 제한 : 2초- 메모리 제한 128MB

 

[문제 풀이]

먼저 문제에서 주어진 예제 2번

5
-1 0 0 2 2

위 예제를 그림으로 나타내보자

위 그림에서 만약 0번이 1번에게 먼저 전화를 한 뒤에 2번에게 전화를 걸면 정답은 4분이 나오게 된다.

하지만 2번에게 먼저 전화를 하게 되면 2번은 0번이 1번에게 전화하는 동안 3번 또는 4번에게 전화 할 수 있기 때문에 첫번째 경우보다 시간이 단축되서 정답이 3분이 되게 된다.

 

위 경우에서 알 수 있는 것은 부하직원에게 전화를 걸때 전화를 걸 사람이 많은 부하직원을 먼저 전화를 해야 올바른 정답을 구할 수 있다.

 

따라서 부하직원 별로 직속 부하들에게 모두 전화를 거는데 필요한 총 소요시간을 구해서 걸리는 시간이 오래걸리는 부하직원순으로 전화를 해주면 정답을 구할 수 있다.

 

추가적으로 각 노드별로 그 직원의 부하직원 전부에게 전화를 다 돌리는데 걸리는 시간은 다음과 같이 구할 수 있다.

 

먼저 그림을 확인해보자

먼저 리프노드들은 0을 항상 리턴해주고

 

부하직원이 있는 직원들은 (부하직원들이 각 걸리는 소요시간 + i) i는 1부터 1씩 증가 한 값중 가장 큰 값을 리턴해주면된다.

 

i값이 1씩 증가하는 이유는 앞에 소요시간이 긴 직원 부터 먼저 전화를 하기 때문에 1분씩 더 걸리는 것을 의미한다.

[소스 코드]

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

#define INF 987654321
#define pii pair<int,int>

using namespace std;

bool cmp(int& a, int& b)
{
	return a > b;
}

typedef struct Node
{
	int cur;
	int parent;
	vector<int> childe;
}Node;

int N;
vector<Node> Nodes;

int solve(int cur)
{
	vector<int> times;

	if (Nodes[cur].childe.size() == 0) return 0;

	for (int i = 0; i < Nodes[cur].childe.size(); i++)
		times.push_back(solve(Nodes[cur].childe[i]));
	
	sort(times.begin(), times.end(), cmp);

	int max_v = -1;
	int tmp = 1;
	for (int i = 0; i < times.size(); i++)
	{
		max_v = max(max_v, times[i] + tmp);
		tmp++;
	}
	return max_v;
}

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

	cin >> N;
	Nodes.resize(N);

	int tmp;
	for (int i = 0; i < N; i++)
	{
		cin >> tmp;
		if (tmp == -1) continue;
		
		Nodes[i].parent = tmp;
		Nodes[tmp].childe.push_back(i);
	}

	cout << solve(0);
}

굳