C++에서 가중치가 완전제곱수인 노드 개수 구하기

문제 설명

각 노드에 가중치가 부여된 이진 트리가 주어졌을 때, 가중치가 완전제곱수(perfect square)인 노드의 개수를 구하는 것이 목표입니다. 예를 들어 어떤 노드의 가중치가 36이라면 36 = 6²이므로 완전제곱수에 해당하며, 이 노드는 개수에 포함됩니다.

예시

입력 1

값을 입력하여 생성한 트리는 다음과 같습니다 −

출력 1

가중치가 완전제곱수인 노드의 개수: 4

설명

트리의 노드들과 각 노드에 연결된 가중치가 주어집니다. 이제 각 노드의 가중치가 완전제곱수인지 하나씩 확인해 보겠습니다.

입력 2

값을 입력하여 생성한 트리는 다음과 같습니다 −

출력 2

가중치가 완전제곱수인 노드의 개수: 2

설명

이번에도 트리의 노드들과 각 노드의 가중치가 주어지며, 각 가중치가 완전제곱수인지 확인합니다.

접근 방식

이 접근 방식에서는 트리를 깊이 우선 탐색(DFS)으로 순회하면서 각 노드의 가중치가 완전제곱수인지 검사합니다. 이를 위해 두 개의 벡터 Node_Weight(100)와 edge_graph[100]을 사용합니다.

• Node_Weight[] 배열을 노드들의 가중치 값으로 초기화합니다.
• 벡터 edge_graph를 이용해 트리를 생성합니다.
• 전역 변수 square를 선언하고 0으로 초기화합니다.
• 함수 check(int check_it)는 정수를 인자로 받아, 그 값이 완전제곱수이면 true를 반환합니다.
• total = sqrt(check_it)를 계산합니다.
• floor(total) != ceil(total)이 참이라면 total은 정수가 아니므로 완전제곱수가 아닙니다. 이 경우 false를 반환합니다.
• 그렇지 않으면 true를 반환합니다.
• 함수 perfect_square(int node, int root)는 현재 노드와 루트 노드를 인자로 받아, 주어진 트리에서 가중치가 완전제곱수인 노드의 개수를 계산합니다.
• check(Node_Weight[node])가 참이면 square를 1 증가시킵니다.
• for 반복문으로 벡터 edge_graph[node]를 순회하며 트리를 탐색합니다.
• 벡터의 다음 노드에 대해 perfect_square(it, node)를 재귀적으로 호출합니다.
• 모든 탐색이 끝나면 square에는 가중치가 완전제곱수인 노드의 총 개수가 저장됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int square = 0;
bool check(int check_it){
    double total = sqrt(check_it);
    if(floor(total) != ceil(total)){
        return false;
    }
    return true;
}
void perfect_square(int node, int root){
    if(check(Node_Weight[node])){
        square++;
    }
    for (int it : edge_graph[node]){
        if(it == root){
            continue;
        }
        perfect_square(it, node);
    }
}
int main(){
    //노드의 가중치
    Node_Weight[2] = 121;
    Node_Weight[1] = 81;
    Node_Weight[4] = 37;
    Node_Weight[3] = 25;
    Node_Weight[8] = 100;
    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);
    perfect_square(2, 2);
    cout<<"가중치가 완전제곱수인 노드의 개수: "<<square;
    return 0;
}

실행 결과

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

가중치가 완전제곱수인 노드의 개수: 4