백준 3085 C++

백준 1135

문제

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. 자기자신은 그들 자기 자신의 직접 또는 간접 상사가 아니고, 모든 직원은 민식이의 직접 또는 간접적인 부하이다.

민식이는 일단 자기 자신의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 뉴스를 들은 후에, 각 부하는 그의 직속 부하에게 한 번에 한 사람씩 전화를 한다. 이 것은 모든 직원이 뉴스를 들을 때 까지 계속된다. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다. 이때 모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

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

입력

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

출력

첫째 줄에 모든 소식을 전하는데 걸리는 시간의 최솟값을 출력한다.

풀이

문제에서 준 힌트는 트리식. 그리고 모든 직원은 정확하게 한 명의 직속 상사가 있다.는 것. 모든 사람은 자신의 직속 부하에게만 전화를 걸 수 있고, 전화는 정확하게 1분 걸린다.

이렇게 3가지다.

언뜻 보기만 하면 DFS다. 그 이유는 결국 트리를 전부 순회하는 데 걸리는 시간을 구하기 때문이다. 하지만 여기서 중요한 점이 하나 있다. 가볍게 넘어갈 수 있지만 중요한 점은 ‘모든 직원이 소식을 듣는데 걸리는 시간의 최솟값을 구하는 것’이라는 점이다. 또한, 상관은 자신의 부하에게 전화를 한 번에 넣을 수 없고, 한 명씩, 그리고 1분이 걸리는 다는 거다.

즉 따라서, 여기서 말하는 건 상관이 누구에게 먼저 전화를 거는 것에 대한 가치판단이 필요하다는 의미가 된다.

간단히 예시를 통해 보자.

똑같은 그래프 구조를 사용함에도 어떤 노드를 먼저 사용하는지에 따른 시간적인 차이가 발생한다.

따라서 처음 입력은 부모가 어떤 자식을 가지고 있는지 입력으로 받는다.

0에서 시작되서 dfs를 돌려보자. 그러면 자식인 1,2에 대한 dfs로 들어간다. 먼저 1로 들어가보자. 그러면 1에서 자식들은 3,4로 들어간다.

3으로 먼저 들어가보자. 3은 자식 노드가 없다. 따라서 while문을 반복할 것도 없으니 0을 return하고, 4도 마찬가지다.

1로 돌아왔다.

1의 pq에는 [0, 0]이 들어가있다.

첫 번째 연락(0 + 1 = 1), 두 번째 연락(0 + 2 = 2) 로 time은 2가 된다.

1기준으로 아래에 있는 모든 노드를 도는데 2초가 걸린다는 말이다.

1에서 나왔다. 그러면 0의 다른 자식인 2로 들어가면, 그건 LeafNode이기 때문에 0을 반환한다.

다시 마침내 0으로 돌아왔다.

0의 pq에는 [2, 0]이 들어가있다.

첫 번째 연락은 (2 + 1 = 3), 두 번째 연락(0 + 2 = 2)로 time의 최댓값은 3이 된다.

이런 식으로 코드가 굴러간다.

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


using namespace std;
int N;
vector<int> tree[51];


//모든 직원이 뉴스를 가장 빠르게 알게 하려면 -> 가장 오래 걸리는 자식 노드부터 연락을 걸어야함. 

int dfs(int cur) {
	priority_queue<int> pq;

	//밑 부하들 돌아다니면서. dfs를 pq에 넣기. 

	//자식들 걸리는 시간을 모두 구해줌. 
	for (int child : tree[cur]) {
		pq.push(dfs(child));
	}

	int time = 0;
	int add = 1;

	while (!pq.empty()) {
		int t = pq.top();
		pq.pop();

		time = max(time, t + add);

		//밑에 있는 자식 1명 마다 시간이 1분씩 늘어남. 
		add++;
	}

	return time;
}


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

	cin >> N;
	
	
	for (int idx = 0; idx < N; ++idx) {
		int parent;
		cin >> parent;
		if (parent != -1) {
			tree[parent].push_back(idx);
		}
	}

	//0에다가 소식 전하기. 
	cout << dfs(0) << "\n";
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기