각 직원에 대해 고유한 ID를 가진 n명의 직원이 있는 회사가 있다고 가정합니다. 이 ID의 범위는 0에서 n - 1입니다. 회사의 대표는 headID를 가진 사람입니다. 각 직원에는 manager[i]가 i 번째 직원의 직속 관리자인 manager[headID] =-1인 관리자 배열에 지정된 한 명의 직속 관리자가 있습니다. 또한 종속 관계가 나무와 같은 구조를 갖는 것이 보장됩니다. 여기서 회사 대표는 회사의 모든 직원에게 긴급한 소식을 알리고 싶어합니다. 그는 그의 직속 부하들에게 알릴 수 있고 그들은 모든 직원이 긴급한 소식을 알 때까지 부하들에게 알릴 것입니다. i 번째 직원은 모든 직속 부하에게 알리기 위해 informTime[i] 분이 필요합니다(따라서 informTime[i]분이 지나면 모든 직속 부하가 뉴스를 퍼뜨릴 수 있습니다). 모든 직원에게 긴급 뉴스를 알리는 데 필요한 시간(분)을 찾아야 합니다. 따라서 입력이 n =6, headID =2, manager =[2,2,-1,2,2,2], infromTime =[0,0,1,0,0,0]인 경우 출력은 1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret :=0
-
크기가 n인 그래프라는 배열을 정의하고 root를 설정합니다. :=-1
-
관리자 배열의 크기까지 범위 0에 있는 i의 경우
-
u :=관리[i] 및 v :=i
-
u가 -1이면 root :=v로 설정하고 다음 반복으로 이동합니다.
-
그래프에 v 삽입[u]
-
-
큐 q를 정의하고, 루트를 q에 삽입하고, 크기가 n인 시간이라는 배열을 정의합니다.
-
q가 비어 있지 않을 때까지
-
curr :=q의 앞 요소, q에서 앞 요소 삭제
-
그래프[curr] 목록의 크기가 0이면 다음 반복으로 건너뜁니다.
-
범위 0에서 그래프 목록의 크기까지 i에 대해 [curr]
-
그래프[curr, i]를 q
에 삽입 -
시간[그래프[curr, i]] :=시간[curr] + informTime[curr]
-
-
-
0 ~ n – 1 범위의 i에 대해:ret :=ret 및 시간의 최대값[i]
-
리턴 렛
예시(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
int ret = 0;
vector <int> graph[n];
int root = -1;
for(int i = 0; i < manager.size(); i++){
int u = manager[i];
int v = i;
if(u == -1) {
root = v;
continue;
}
graph[u].push_back(v);
}
queue <int> q;
q.push(root);
vector <int> time(n);
while(!q.empty()){
int curr = q.front();
q.pop();
if(!graph[curr].size()) continue;
for(int i = 0; i < graph[curr].size(); i++){
q.push(graph[curr][i]);
time[graph[curr][i]] = time[curr] + informTime[curr];
}
}
for(int i = 0; i <n; i++)ret = max(ret, time[i]);
return ret;
}
};
main(){
vector<int> v = {2,2,-1,2,2,2}, v1 = {0,0,1,0,0,0};
Solution ob;
cout << (ob.numOfMinutes(6, 2, v, v1));
} 입력
6 2 [2,2,-1,2,2,2] [0,0,1,0,0,0]
출력
1