이 글에서는 N-ary(다진) 트리에서 특정 노드의 형제(sibling) 노드 개수를 구하는 방법을 자세히 알아봅니다. 사용자가 지정한 키(key) 값과 일치하는 노드를 찾아 그 노드의 형제 수를 출력하고, 해당 값을 가진 노드가 존재하지 않는다면 -1을 출력해야 합니다. 이 문제는 다음과 같은 한 가지 접근법으로 해결할 수 있습니다.
단순 접근법
이 방법에서는 트리의 모든 노드를 순회하면서 각 부모 노드의 자식 중 사용자가 입력한 값과 동일한 키를 가진 자식이 있는지 확인합니다. 그런 자식이 존재한다면 정답은 '부모가 가진 자식 수 - 1'이 됩니다. 자기 자신을 제외한 나머지 자식들이 모두 형제이기 때문입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Node { // 트리 노드의 구조.
public:
int key;
vector<Node*> child;
Node(int data){
key = data;
}
};
int main(){
// 트리 생성
Node* Base = new Node(50);
(Base->child).push_back(new Node(2));
(Base->child).push_back(new Node(30));
(Base->child).push_back(new Node(14));
(Base->child).push_back(new Node(60));
(Base->child[0]->child).push_back(new Node(15));
(Base->child[0]->child).push_back(new Node(25));
(Base->child[0]->child[1]->child).push_back(new Node(70));
(Base->child[0]->child[1]->child).push_back(new Node(100));
(Base->child[1]->child).push_back(new Node(6));
(Base->child[1]->child).push_back(new Node(1));
(Base->child[2]->child).push_back(new Node(7));
(Base->child[2]->child[0]->child).push_back(new Node(17));
(Base->child[2]->child[0]->child).push_back(new Node(99));
(Base->child[2]->child[0]->child).push_back(new Node(27));
(Base->child[3]->child).push_back(new Node(16));
int x = 30;
queue<Node*> q;
q.push(Base);
bool flag = 0;
int answer = -1;
if(Base -> key != x){
while(!q.empty()){
auto parent = q.front();
q.pop();
for(int i = 0; i < parent -> child.size(); i++){
if(parent -> child[i] -> key == x){
answer = parent -> child.size() - 1;
flag = 1;
break;
}
q.push(parent -> child[i]);
}
if(flag)
break;
}
cout << answer << "\n";
}
else
cout << "0\n";
return 0;
}
출력 결과
3
프로그램 설명
이 프로그램은 아직 방문하지 않은 노드들을 담아 두는 큐(queue)를 활용합니다. 큐에서 노드를 하나 꺼내(pop) 방문 처리한 뒤, 해당 노드의 모든 자식을 탐색합니다. 탐색 도중 어떤 자식의 키 값이 x와 일치하면 플래그(flag)를 설정하고, 정답 변수에 '자식 수 - 1'을 대입한 후 for 반복문을 빠져나옵니다. 이후 플래그가 설정되었는지 확인하여, 설정되어 있다면 while 반복문 역시 종료하고 최종적으로 정답을 출력합니다.
만약 주어진 값을 가진 노드가 트리에 존재하지 않는다면, 정답 변수는 초기값인 -1 그대로 유지되므로 결과적으로 -1이 출력됩니다. 또한 루트 노드의 값이 입력값과 같은 경우에는 형제가 존재할 수 없으므로, 이를 검사하는 if 문을 통해 0을 출력하도록 처리했습니다.
결론
이 글에서는 N-ary 트리에서 주어진 노드의 형제 수를 구하는 문제를 O(N) 시간 복잡도로 해결했습니다. 너비 우선 탐색(BFS) 기반의 전체 풀이 과정과 C++ 구현 코드를 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다.