✍ 문제
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.
현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.
이제 리프 노드의 개수는 1개이다.
✍ 입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다.
둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다.
만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
✍ 출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
✅ 코드
#include <iostream>
#include <algorithm>
#include <vector>
#define _CRTDBG_MAP_ALLOC
#include <crtdbg.h>
using namespace std;
struct Node {
int data;
vector<int> child;
};
Node* createNode(int num) {
Node* newnode = new Node;
newnode->data = num;
return newnode;
}
void deleteNode(vector<Node*>& tree, Node* node) {
if (node->child.size() == 0) node->data = -1;
else {
for (int i = 0; i < node->child.size(); i++) {
int data = node->child[i];
deleteNode(tree, tree[data]);
}
node->data = -1;
}
}
int main() {
int num, delete_data;
int result = 0;
vector<Node*> tree;
vector<pair<int, int>> standby;
cin >> num;
for (int i = 0; i < num; i++) {
int parent_data;
cin >> parent_data;
tree.push_back(createNode(i));
if (parent_data != -1 && i > parent_data) (tree[parent_data]->child).push_back(i);
else if (i < parent_data) standby.push_back(make_pair(i, parent_data)); //보류
}
for (int i = 0; i < standby.size(); i++) { //보류한 값들에 대한 child 추가
int parent = standby[i].second;
tree[parent]->child.push_back(standby[i].first);
}
cin >> delete_data; //삭제해야할 노드의 data
deleteNode(tree, tree[delete_data]);
for (int i = 0; i < num; i++) {
if (tree[i]->data != -1 && tree[i]->child.size() == 0) result++;
if (tree[i]->child.size() == 1 && tree[i]->child[0] == delete_data) result++;
delete tree[i]; //동적할당한 노드들에 대한 메모리 해제
}
_CrtDumpMemoryLeaks();
cout << result;
return 0;
}✅ 코드풀이
❗ 알고리즘
이번 문제의 알고리즘은 트리 생성과 노드 삭제 두 부분으로 나누어 설명을 해보도록 하겠다.
1. 트리 생성
이 문제는 특정 노드를 삭제할 시, 그 노드가 root인 서브트리 전체를 삭제해야 한다. 따라서 각 노드는 그들의 자식 노드들에 대한 정보 (child 벡터) 를 가지고 있어야 한다.
struct Node {
int data;
vector<int> child;
};입력값에 대해 살펴보자. 총 N개의 숫자를 입력받는데 이 중 p번째 입력값이 q라고 한다면,
p가 노드의 data 값이 되고, q가 부모노드의 data 값이 된다. 따라서 p번째로 q라는 값이 들어온다면
1) p를 data로 가지는 노드를 새로 생성하고
2) q를 data로 가지는 노드의 child 벡터에 q를 push_back 해주어야 한다.
1에 대해서는 createNode 함수를 통해 node를 동적할당하고 data를 p로 초기화 해주기만 하면 된다.
다만 2번에서 고려해야할 사항이 생기는데, 바로 p 값이 q 값보다 작아서 tree 벡터에 q를 data로 가지는 노드가 아직 없는 경우이다. 각 노드의 data는 0, 1, 2 ... 처럼 0부터 오름차순 순서대로 저장되기 때문에 자식노드의 data < 부모노드의 data 인 경우 아직 부모노드가 tree에 저장되지 않아 child 벡터에 추가할 수 없는 상황이 발생한다.
이 경우를 대비에 해당 (p, q)를 pair 형태로 저장하는 standby 벡터를 선언하였다. 총 N회의 반복문을 1차로 돌며 자식노드의 data > 부모노드의 data인 경우만 부모노드의 child에 자식노드의 data를 push하고, 2차로 standby.size( )만큼 반목문을 돌며 1차 반복에서 보류되었던 값들을 올바른 부모노드의 child 벡터에 push해준다.
for (int i = 0; i < num; i++) {
int parent_data;
cin >> parent_data;
tree.push_back(createNode(i));
if (parent_data != -1 && i > parent_data) (tree[parent_data]->child).push_back(i);
else if (i < parent_data) standby.push_back(make_pair(i, parent_data)); //보류
}▲ 1차로 num번 반복을 하며 node 생성 및 child 처리
for (int i = 0; i < standby.size(); i++) { //보류한 값들에 대한 child 추가
int parent = standby[i].second;
tree[parent]->child.push_back(standby[i].first);
}▲ 2차로 standby.size( )번 반복을 하며 보류된 값에 대한 child 처리
2. 노드 삭제
삭제할 노드의 data값을 입력값으로 받게되는데 tree 벡터에 data값의 오름차순으로 저장되어 있기 때문에 입력값이 delete_data라면 삭제해야할 노드는 tree[delete_node]라는 것을 간단히 구할 수 있다.
이번 문제의 삭제 부분에서 가장 중요한 것은 해당 노드만 삭제하는 것이 아니라, 해당 노드의 모든 서브트리까지 삭제해야 하는 것이다. 따라서 deleteNode( )의 재귀적 호출을 통해 모든 자식노드들을 삭제시킨다. 이때 아예 tree에서 erase해버리면 tree의 index 값을 노드의 data와 같게 사용하지 못하기 때문에 data를 -1로 바꾸어 삭제된 노드임을 알 수 있게 하였다.
void deleteNode(vector<Node*>& tree, Node* node) {
if (node->child.size() == 0) node->data = -1;
else {
for (int i = 0; i < node->child.size(); i++) {
int data = node->child[i];
deleteNode(tree, tree[data]);
}
node->data = -1;
}
}마지막으로 리프노드의 개수를 구할 때는 Node가 저장되어 있는 (엄밀히 말하자면 Node 포인터가 저장되어 있는) tree 벡터를 차례로 순회하며 data != -1 이고 child.size( ) == 0인 노드의 개수를 구한다.
이번 문제는 어떻게 트리를 다루고, 삭제를 해야하는지에 대한 알고리즘 성립에 꽤 시간을 썼던 것 같다. 그런데 뭔가 풀면서 재미있다고 느낀 문제는 오랜만이어서 기분이 좋았다 😜 자구알을 다시 차근차근 공부를 하다보니 확실이 PS에서도 너무너무 도움이 되고 탄탄해진 (물론 아직 한참 부족하지만) 느낌이라 나름 뿌듯하다아 🍀
