Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 회사의 모든 직원에게 소식을 전달하는 데 필요한 시간 구하기

문제 개요

n명의 직원이 있는 회사가 있다고 가정해 봅시다. 각 직원은 0부터 n-1까지의 고유한 ID를 가지며, 회사의 대표(CEO)는 headID에 해당하는 직원입니다. 각 직원은 한 명의 직속 상사를 가지며, manager 배열에서 manager[i]는 i번째 직원의 직속 상사를 의미합니다. 단, 대표자의 경우 manager[headID] = -1입니다. 또한 상하 관계는 항상 트리(tree) 형태의 구조를 이룬다는 것이 보장됩니다.

대표는 회사의 긴급한 소식을 모든 직원에게 전달하려고 합니다. 대표가 먼저 자신의 직속 부하들에게 소식을 알리면, 그 부하들이 다시 자신의 부하들에게 전달하는 방식으로 소식이 퍼져 나갑니다. i번째 직원이 자신의 모든 직속 부하에게 소식을 전달하는 데는 informTime[i]분이 걸립니다. 즉, informTime[i]분이 지난 후에야 그의 직속 부하들이 소식을 전파하기 시작할 수 있습니다.

우리가 구해야 하는 것은 모든 직원에게 긴급 소식이 전달되기까지 걸리는 총 시간(분)입니다.

예를 들어 입력이 n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]이라면 출력은 1이 됩니다.

풀이 접근 방법

이 문제는 조직도가 트리 구조를 이루므로, 너비 우선 탐색(BFS)을 활용해 해결할 수 있습니다. 각 노드에 도달하는 시점의 시간을 기록하고, 그중 최댓값을 구하면 됩니다. 단계별로 살펴보면 다음과 같습니다.

  • 결과값 ret := 0으로 초기화합니다.
  • 크기가 n인 인접 리스트 graph를 정의하고, root := -1로 설정합니다.
  • i를 0부터 manager 배열의 크기까지 반복합니다.
    • u := manager[i], v := i로 설정합니다.
    • u가 -1이라면 root := v로 지정하고 다음 반복으로 넘어갑니다.
    • 그렇지 않으면 v를 graph[u]에 추가합니다.
  • 큐 q를 정의하고 root를 삽입한 뒤, 크기가 n인 time 배열을 선언합니다.
  • q가 빌 때까지 다음을 반복합니다.
    • curr := q의 맨 앞 요소를 꺼내고 pop합니다.
    • graph[curr]의 크기가 0이면(부하가 없으면) 다음 반복으로 건너뜁니다.
    • i를 0부터 graph[curr]의 크기까지 반복하며:
      • graph[curr][i]를 q에 삽입합니다.
      • time[graph[curr][i]] := time[curr] + informTime[curr]로 갱신합니다.
  • i를 0부터 n-1까지 순회하며 ret := max(ret, time[i])로 최댓값을 갱신합니다.
  • ret을 반환합니다.

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

정리

이 알고리즘은 manager 배열을 이용해 조직도를 인접 리스트 형태의 트리로 변환한 뒤, 대표(root)에서부터 BFS를 수행하면서 각 직원이 소식을 받게 되는 시점을 time 배열에 기록합니다. 마지막으로 time 배열의 최댓값이 곧 모든 직원에게 소식이 전달되는 데 걸리는 총 시간이 됩니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 효율적입니다.