Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 트리 노드 삭제하기: 노드 값의 합이 0인 서브트리 제거 방법

노드 0을 루트로 하는 트리가 하나 있다고 가정해 보겠습니다. 이 트리는 다음과 같은 정보로 주어집니다.

  • 노드의 총 개수는 nodes
  • i번째 노드의 값은 value[i]
  • i번째 노드의 부모는 parent[i]

우리가 해야 할 작업은 노드 값들의 합이 0이 되는 모든 서브트리를 제거하고, 그 후 트리에 남아 있는 노드의 개수를 반환하는 것입니다.

예를 들어 다음과 같은 트리가 있다고 가정해 봅시다.

C++로 트리 노드 삭제하기: 노드 값의 합이 0인 서브트리 제거 방법

총 7개의 노드가 있고, 이 경우 출력 결과는 2가 됩니다.

문제 해결 접근 방법

이 문제는 DFS(깊이 우선 탐색)를 활용하면 효율적으로 해결할 수 있습니다. 각 서브트리의 값 합계와 노드 개수를 재귀적으로 계산한 뒤, 합이 0이면 해당 서브트리 전체를 제거 대상으로 처리하는 방식입니다.

알고리즘 단계

  1. children이라는 이름의 맵(map)을 생성합니다.
  2. dfs() 메서드를 정의합니다. 이 메서드는 노드 번호, 값 배열, 그래프를 인자로 받습니다.
  3. temp를 (value[node], 1) 형태의 페어(pair)로 초기화합니다. 첫 번째 요소는 서브트리 값의 합, 두 번째 요소는 노드 개수를 의미합니다.
  4. 현재 노드의 자식들을 순회하며 각 자식에 대해 dfs()를 재귀 호출하고, 반환된 페어의 값을 누적합니다.
    • temp.first에 자식의 합계를 더합니다.
    • temp.second에 자식의 노드 개수를 더합니다.
  5. 순회가 끝난 후 temp.first(서브트리 값의 합)가 0이라면, ans에서 temp.second(해당 서브트리의 노드 수)만큼 빼고, temp.second를 0으로 설정합니다.
  6. temp를 반환합니다.

메인 메서드 처리 과정

  1. nodes, parent 배열, value 배열을 입력으로 받습니다.
  2. n은 value 배열에 있는 값의 개수입니다.
  3. ans를 n으로 초기화합니다(처음에는 모든 노드가 남아 있다고 가정).
  4. 크기가 n + 1인 그래프 배열을 정의합니다.
  5. i가 1부터 n-1까지일 때, i를 graph[parent[i]]에 삽입하여 부모-자식 관계를 구성합니다.
  6. dfs(0, value, graph)를 호출하여 루트부터 탐색을 시작합니다.
  7. ans를 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   map <int, int> children;
   int ans;
   pair <int, int> dfs(int node, vector<int>& value, vector <int> graph[]){
      pair <int, int> temp = {value[node], 1};
      for(int i = 0; i < graph[node].size(); i++){
         pair <int, int> temp2 = dfs(graph[node][i], value, graph);
         temp.first += temp2.first;
         temp.second += temp2.second;
      }
      if(temp.first == 0){
         ans -= temp.second;
         temp.second = 0;
      }
      return temp;
   }
   int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
      int n = value.size();
      ans = n;
      children.clear();
      vector < int > graph[n + 1];
      for(int i = 1; i < n; i++){
         graph[parent[i]].push_back(i);
      }
      dfs(0, value, graph);
      return ans;
   }
};
main(){
   vector<int> v1 = {-1,0,0,1,2,2,2};
   vector<int> v2 = {1,-2,4,0,-2,-1,-1};
   Solution ob;
   cout << (ob.deleteTreeNodes(7,v1, v2));
}

입력

7
[-1,0,0,1,2,2,2]
[1,-2,4,0,-2,-1,-1]

출력

2

동작 원리 설명

위 예제에서 루트 노드 0의 값은 1이며, 두 개의 자식 노드(값 -2와 4)를 가지고 있습니다. DFS 탐색 과정에서 각 서브트리의 값 합계가 계산되며, 합이 0이 되는 서브트리(예: 값이 0인 노드, 또는 -2, -1, -1로 합이 0이 되는 서브트리)는 제거됩니다. 최종적으로 남는 노드는 루트 노드와 값이 4인 노드뿐이므로 출력은 2가 됩니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 각 노드를 정확히 한 번씩 방문하기 때문에 효율적입니다.