C++로 트리 노드 중 가중치 자릿수의 합이 홀수인 노드 개수 세기

문제 소개

각 노드에 가중치가 할당된 이진 트리가 주어졌을 때, 목표는 노드 가중치의 자릿수 합이 홀수가 되는 노드의 개수를 찾는 것입니다. 예를 들어 가중치가 12라면 자릿수의 합은 1+2=3으로 홀수이므로 해당 노드를 셉니다.

예시

입력

값을 입력한 후 생성되는 트리는 아래와 같습니다 −

출력

가중치 자릿수의 합이 홀수인 노드의 개수: 2

설명

트리의 각 노드와 노드에 연결된 가중치가 주어집니다.
이제 모든 가중치의 자릿수 합을 계산하고 홀수인지 여부를 확인합니다.

입력

값을 입력한 후 생성되는 트리는 아래와 같습니다 −

출력

가중치 자릿수의 합이 홀수인 노드의 개수: 4

설명

트리의 각 노드와 노드에 연결된 가중치가 주어집니다.
이제 모든 가중치의 자릿수 합을 계산하고 홀수인지 여부를 확인합니다.

접근 방식

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다. −

이 접근 방식에서는 트리를 순회하기 위해 DFS(깊이 우선 탐색)를 적용하고, 각 노드의 가중치 자릿수 합이 홀수인지 확인합니다. 이를 위해 두 개의 벡터 Node_Weight(100)와 edge_graph[100]를 사용합니다.

• Node_Weight[] 배열을 노드들의 가중치 값으로 초기화합니다.
• 벡터 edge_graph를 사용하여 트리를 생성합니다.
• 전역 변수 sum을 선언하고 0으로 초기화합니다.
• 함수 sum_total(int check)는 정수를 입력받아 그 자릿수의 합을 반환합니다.
• 초기 합을 total=0으로 설정합니다.
• while 루프를 사용하여 가장 오른쪽 자릿수(check % 10)를 계산해 total에 더하고, check를 10으로 나누어 줄입니다.
• total을 check의 자릿수 합으로 반환합니다.
• 함수 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