C++로 트리를 순회하며 가중치가 2의 거듭제곱인 노드 개수 구하기

각 노드에 가중치가 할당된 이진 트리가 주어졌을 때, 가중치가 2의 거듭제곱인 노드의 개수를 구하는 것이 목표입니다. 예를 들어 어떤 노드의 가중치가 32라면 32는 2⁵이므로 이 노드는 개수에 포함됩니다.

예제 입력 및 출력

입력

값을 입력하면 아래와 같은 트리가 생성됩니다.

출력

가중치가 2의 거듭제곱인 노드의 개수: 3

설명

각 노드에는 고유한 번호와 그에 대응하는 가중치가 주어져 있습니다. 모든 노드의 가중치를 하나씩 확인하여 해당 값이 2의 거듭제곱으로 표현되는지 검사한 뒤, 조건을 만족하는 노드만 셉니다.

따라서 가중치가 2의 거듭제곱인 노드는 2번(가중치 8), 3번(가중치 16), 9번(가중치 32)으로 총 3개입니다.

프로그램에서 사용하는 접근 방식

이 문제는 DFS(깊이 우선 탐색)를 이용해 트리를 순회하면서 각 노드의 가중치가 2의 거듭제곱인지 확인하는 방식으로 해결합니다. 이를 위해 두 개의 벡터 Node_Weight(100)와 edge_graph[100]를 준비합니다.

• 가중치 초기화: Node_Weight[] 배열에 각 노드의 가중치를 저장합니다.
• 트리 생성: edge_graph 벡터 배열에 간선 정보를 추가하여 트리를 구성합니다.
• 카운터 변수: 전역 변수 power를 선언하고 0으로 초기화합니다.
• 재귀 함수 정의: power_two(int node, int root) 함수는 현재 노드와 부모 노드를 인자로 받아, 해당 서브트리 전체에서 가중치가 2의 거듭제곱인 노드의 개수를 계산합니다.
• 2의 거듭제곱 판별: 비트 AND 연산을 활용합니다. 양의 정수 n이 2의 거듭제곱일 필요충분조건은 (n & (n − 1)) == 0이라는 것입니다. 예를 들어 32는 이진수로 100000이고 31은 011111이므로, 두 값을 AND하면 0이 됩니다.
• 판별 조건이 참이면 해당 노드의 가중치가 2의 거듭제곱이므로 power 값을 1 증가시킵니다.
• for 루프로 edge_graph[node]에 연결된 인접 노드들을 순회하면서, 바로 직전에 방문한 부모 노드는 건너뛰고 나머지 노드에 대해 power_two(it, node)를 재귀 호출합니다.
• 모든 재귀 호출이 종료되면 power에는 트리 전체에서 가중치가 2의 거듭제곱인 노드의 총개수가 저장됩니다.

예제 코드 (C++)

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int powers = 0;

void power_two(int node, int root){
    int set = Node_Weight[node];
    if(set && (!(set & (set - 1)))){
        powers++;
    }
    for(int it : edge_graph[node]){
        if(it == root){
            continue;
        }
        power_two(it, node);
    }
}

int main(){
    // 노드의 가중치 설정
    Node_Weight[2] = 8;
    Node_Weight[1] = 100;
    Node_Weight[4] = 211;
    Node_Weight[3] = 16;
    Node_Weight[8] = 7171;
    Node_Weight[9] = 32;
    // 트리의 간선 정보 생성
    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);
    power_two(2, 2);
    cout<<"가중치가 2의 거듭제곱인 노드의 개수: "<<powers;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

가중치가 2의 거듭제곱인 노드의 개수: 3

복잡도 분석

시간 복잡도는 트리의 모든 노드를 정확히 한 번씩 방문하므로 O(N)입니다. 공간 복잡도는 재귀 호출 스택과 인접 리스트 저장에 O(N)이 소요됩니다. 또한 비트 연산 기반 판별 덕분에 각 노드의 검사가 상수 시간 O(1) 안에 처리되어 전체 알고리즘이 매우 효율적입니다.