C++로 트리에서 홀수·짝수 노드를 가진 모든 레벨 출력하기

이 문제에서는 하나의 트리가 주어지며, 각 레벨(level)에 포함된 노드의 개수를 기준으로 노드 수가 홀수인 레벨과 노드 수가 짝수인 레벨을 구분하여 모두 출력해야 합니다.

예시를 통해 개념을 더 자세히 이해해 보겠습니다.

출력 결과 −

노드 수가 홀수인 레벨: 1, 3, 4
노드 수가 짝수인 레벨: 2

설명 − 1번째 레벨에는 노드가 1개(홀수), 2번째 레벨에는 2개(짝수), 3번째 레벨에는 3개(홀수), 4번째 레벨에는 3개(홀수)가 존재합니다. 따라서 홀수 레벨은 1, 3, 4이고 짝수 레벨은 2입니다.

이 문제를 해결하려면 먼저 각 레벨에 속한 노드의 개수를 구한 뒤, 그 개수가 홀수인지 짝수인지에 따라 레벨을 분류하여 출력해야 합니다.

다음 단계를 따라 해결할 수 있습니다 −

1단계 − height[node] = 1 + height[parent] 공식을 이용해 각 노드의 높이(레벨)를 계산하며 트리를 탐색합니다.

2단계 − 각 레벨에 속한 노드의 개수를 배열에 저장합니다.

3단계 − 레벨별 노드 개수가 담긴 배열을 순회하면서 홀수 레벨과 짝수 레벨을 각각 출력합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
void traversal(int node, int parent, int height[], int vis[], vector<int> tree[]){
    height[node] = 1 + height[parent];
    vis[node] = 1;
    for (auto it : tree[node]) {
       if (!vis[it]) {
          traversal(it, node, height, vis, tree);
       }
    }
}
void insert(int x, int y, vector<int> tree[]){
    tree[x].push_back(y);
    tree[y].push_back(x);
}
void evenOddLevels(int N, int vis[], int height[]){
    int mark[N + 1];
    memset(mark, 0, sizeof mark);
    int maxLevel = 0;
    for (int i = 1; i <= N; i++) {
       if (vis[i])
          mark[height[i]]++;
       maxLevel = max(height[i], maxLevel);
    }
    cout << "노드 수가 홀수인 레벨: ";
    for (int i = 1; i <= maxLevel; i++) {
       if (mark[i] % 2)
          cout << i << " ";
    }
    cout << "\n노드 수가 짝수인 레벨: ";
    for (int i = 1; i <= maxLevel; i++) {
       if (mark[i] % 2 == 0)
          cout << i << " ";
    }
}
int main(){
    const int N = 9;
    vector<int> tree[N + 1];
    insert(1, 2, tree);
    insert(1, 3, tree);
    insert(2, 4, tree);
    insert(2, 5, tree);
    insert(5, 7, tree);
    insert(5, 8, tree);
    insert(3, 6, tree);
    insert(6, 9, tree);
    int height[N + 1];
    int vis[N + 1] = { 0 };
    height[0] = 0;
    traversal(1, 0, height, vis, tree);
    evenOddLevels(N, vis, height);
    return 0;
}

실행 결과

노드 수가 홀수인 레벨: 1 3 4
노드 수가 짝수인 레벨: 2