深さ優先探索を用いて社長のお給料を決める
問題
C: 高橋君の給料 - AtCoder Beginner Contest 026 | AtCoder
解き方
問題の入力値から、上司と部下の関係をグラフを起こす。すると、今回の問題では部下に対する上司の人数は必ず１人なので木構造になる。 根ノードは社長になり、葉ノードは部下を持たない社員となる。また、問題の性質上、社長の給料は社長の直属の部下の全てのお給料が計算されて初めて決定する。よって社員を持たない部下のお給料から計算していけば最終的に社長の給料を決定することができる。
ソースコードは最後に添付する。
上司と部下の関係をグラフに起こす
グラフ構造を実装するには幾つかの方法ああるが今回は社員を管理するWorkerクラスを作成し、そのプロパティとして部下のリストを持たせる(subordinates)。他には隣接行列を作成する方法もあるが今回は触れない。
深さ優先探索を用いて部下を持たない社員から計算する
今回は深さ優先探索を用いた再帰処理で計算していく。再帰処理をする関数を作りにあたり以下をポイントとする。
- 求めたいもの: お給料(int)
- 深さが変わる度に変わるもの: どの社員の給料を計算しているか(Worker)
- 再帰を抜ける条件: 今計算しようとしている社員に部下が存在しない時
以上をポイントとして関数を作る。
計算量はどうか
全ての社員の給料を計算しているので計算量はO(N)となり、Nの最大値は20なので問題ない。
また、社長の給料の最大値はN^2 -1であり、大体10*6になりInt型で問題ない。
