C++で木の中から重みの桁和が奇数となるノードを数える方法

各ノードに重みが割り当てられた二分木が与えられます。この問題の目標は、重みの各桁の合計（桁和）が奇数になるノードの個数を求めることです。たとえば、重みが「12」であれば桁和は 1+2=3 となり奇数なので、このノードはカウントの対象になります。

例

入力

入力された値から作成される木は次のとおりです。

出力

与えられた木のうち、重みの桁和が奇数であるノードの数：2

説明

木の各ノードと、それぞれに対応する重みが与えられています。
すべての重みについて桁和を計算し、それが奇数かどうかを判定します。

入力

入力された値から作成される木は次のとおりです。

出力

与えられた木のうち、重みの桁和が奇数であるノードの数：4

説明

木の各ノードと、それぞれに対応する重みが与えられています。
すべての重みについて桁和を計算し、それが奇数かどうかを判定します。

以下のプログラムで採用しているアプローチは次のとおりです。

このアプローチでは、木に対してDFS（深さ優先探索）を適用して走査を行い、各ノードの重みの桁和が奇数かどうかを確認します。そのために、Node_Weight(100) と edge_graph[100] という2つのベクターを用意します。

• Node_Weight[] を各ノードの重みで初期化します。
• ベクター edge_graph を使って木（グラフ）を構築します。
• グローバル変数 sum を宣言し、0 で初期化します。
• 関数 sum_total(int check) は整数を受け取り、その桁和を返します。
• 初期値として total=0 を設定します。
• while ループの中で、check % 10 によって最下位の桁を取り出して total に加算し、check を 10 で割りながら更新していきます。
• check の桁和である total を返します。
• 関数 odd_weight(int node, int root) はノードとその親ノードを受け取り、重みの桁和が奇数であるノードの数を返します。
• total = sum_total(Node_Weight[node]) として、そのノードの重みの桁和を計算します。
• total % 2 == 1 であれば奇数なので、sum をインクリメントします。
• 隣接リスト内の次のノードに対して odd_weight(it, node) を再帰的に呼び出します。
• すべての処理が完了した時点で、sum には重みの桁和が奇数となるノードの総数が格納されます。

例

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int sum = 0;
int sum_total(int check){
    int total = 0;
    while(check){
        total += check % 10;
        check = check / 10;
    }
    return total;
}
void odd_weight(int node, int root){
    int total = sum_total(Node_Weight[node]);
    if (total % 2 == 1){
        sum++;
    }
    for (int it : edge_graph[node]){
        if(it == root){
            continue;
        }
        odd_weight(it, node);
    }
}
int main(){
    //ノードの重み
    Node_Weight[2] = 23;
    Node_Weight[1] = 141;
    Node_Weight[4] = 211;
    Node_Weight[3] = 115;
    Node_Weight[8] = 7171;
    Node_Weight[9] = 701;
    //グラフの辺を作成
    edge_graph[2].push_back(1);
    edge_graph[2].push_back(4);
    edge_graph[4].push_back(3);
    edge_graph[4].push_back(8);
    edge_graph[8].push_back(9);
    odd_weight(2, 2);
    cout<<"与えられた木のうち、重みの桁和が奇数であるノードの数："<<sum;
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

与えられた木のうち、重みの桁和が奇数であるノードの数：2