C++で全従業員に緊急ニュースを伝えるのに必要な時間を求める方法(BFS活用)

問題の概要

ある会社にはn人の従業員が在籍しており、各従業員には0からn-1までの一意なIDが割り振られています。会社のトップ(社長)はheadIDで表されます。各従業員には必ず一人の直属の上司が存在し、それはmanager配列によって与えられます。manager[i]はi番目の従業員の直属の上司を意味し、社長の場合はmanager[headID] = -1となります。なお、組織の上下関係は木構造になっていることが保証されています。

社長は緊急のニュースを全従業員に伝えたいと考えています。まず社長が直属の部下に連絡し、その部下たちがさらに自分の部下へと伝えていくことで、ニュースは組織全体へと広まっていきます。i番目の従業員が直属の部下全員への通知を完了するまでにかかる時間はinformTime[i]分です。つまり、informTime[i]分が経過すると、その直属の部下たちは次の人々へニュースを伝え始めることができます。

このとき、全従業員に緊急ニュースが行き渡るまでに必要な合計時間(分)を求めるのが本問題の目的です。

例えば、入力がn = 6、headID = 2、manager = [2,2,-1,2,2,2]、informTime = [0,0,1,0,0,0]である場合、出力は1になります。社長(ID: 2)が5人の直属の部下全員に通知を完了するのに1分かかり、部下たち自身の通知時間は0分のため、組織全体への伝達はわずか1分で完了します。

解法のアプローチ

この問題は、組織図をグラフ(隣接リスト)として構築し、社長を起点とした幅優先探索(BFS)を行うことで効率的に解けます。各従業員がニュースを受け取る時刻を記録していき、その最大値が答えとなります。

具体的な手順は以下の通りです。

1. 答えとなるretを0で初期化します。

2. サイズnの隣接リストgraphを用意し、rootを-1で初期化します。

3. iを0からmanager配列のサイズまでループさせます。

   • u := manager[i]、v := i とします。

   • uが-1の場合は、root := v として次の反復へ進みます。

   • それ以外は、graph[u]にvを追加します。

4. キューqを用意してrootを追加し、各従業員がニュースを受け取る時刻を記録するサイズnの配列timeを定義します。

5. qが空になるまで以下を繰り返します。

   • currにqの先頭要素を取り出して削除します。

   • graph[curr]が空(部下がいない)の場合は、次の反復へスキップします。

   • iを0からgraph[curr]のサイズまでループさせます。

     • graph[curr][i]をqに追加します。

     • time[graph[curr][i]] := time[curr] + informTime[curr] と更新します。

6. iを0からn-1までループさせ、ret := max(ret, time[i]) として最大値を求めます。

7. 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

この実装では、BFSにより上から順に各従業員へニュースが届く時刻を累積的に計算しています。最終的にtime配列の最大値を取ることで、最も遅くニュースを受け取る従業員の時刻、すなわち全従業員への通知完了に必要な時間が求められます。計算量はO(n)となり、非常に効率的です。