Pythonで従業員の重要度合計を求めるアルゴリズム(BFSを使った解法)

問題の概要

従業員情報を表すデータ構造を考えてみましょう。各従業員には「一意のID」「重要度(importance)の値」「直属の部下のIDリスト」が含まれています。

例として、従業員1が従業員2の上司であり、従業員2が従業員3の上司であるケースを見てみます。それぞれの重要度が15、10、5である場合、データ構造は次のようになります。

• 従業員1:[1, 15, [2]]
• 従業員2:[2, 10, [3]]
• 従業員3:[3, 5, []]

このように会社全体の従業員情報と特定の従業員IDが与えられたとき、「その従業員本人と、すべての部下(間接的な部下も含む)の重要度の合計」を求めるのが本記事のゴールです。

入力例と出力例

入力が [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]] と 1 の場合、出力は 11 になります。理由は以下の通りです。

• 従業員1の重要度は5
• 従業員1には直属の部下が2人(従業員2と従業員3)いる
• 従業員2と従業員3の重要度はそれぞれ3

したがって、従業員1の重要度の合計は 5 + 3 + 3 = 11 となります。

解法のアプローチ

この種の組織階層をたどる問題は、BFS(幅優先探索)を使うと効率的に解けます。手順は以下の通りです。

1. 重要度を格納する辞書(weight)と、部下のIDリストを格納する辞書(leader)を用意する
2. すべての従業員情報を走査し、従業員IDをキーとして重要度と部下リストを登録する
3. 結果変数(res)を0で初期化し、対象の従業員自身の重要度を加算する
4. キューに直属の部下のIDを追加する
5. キューが空になるまで次の処理を繰り返す
   • キューから要素を1つ取り出す
   • その従業員の重要度を結果に加算する
   • さらに部下が存在すれば、そのIDをキューに追加する
6. 最終的な合計値(res)を返す

Pythonでの実装例

class Solution(object):
    def getImportance(self, employees, id):
        weight = {}
        leader = {}
        for e in employees:
            weight[e[0]] = e[1]
            leader[e[0]] = e[2]
        res = 0
        res += weight[id]
        queue = leader[id]
        while queue:
            new_queue = []
            node = queue.pop()
            res += weight[node]
            if leader[node]:
                new_queue += leader[node]
            queue += new_queue
        return res

ob = Solution()
print(ob.getImportance([[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1))

入力

[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1

出力

11

計算量の目安

このアルゴリズムでは、すべての従業員を最大1回ずつ訪問します。そのため、従業員数をNとすると、時間計算量・空間計算量はともにO(N)となります。組織図が深くなっても効率よく処理できる点が、BFSを用いた解法の大きなメリットです。