트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다.
[입력] 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
[출력] 첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
✅ 문제 풀이
각 노드에 대한 자식 노드를 저장하기 위해서, vector 형태의 크기가 50인 배열 tree을 생성해주었다. vector<int> tree[50]
입력으로 N이 1부터 50까지 들어올 수 있기 때문에, 노드는 0~49임을 고려한 것이다.
차례대로 입력받을 때 0번 노드부터 부모를 입력받는다.
따라서 -1인 경우를 제외하고, 나머지 경우에 대해서는 입력받은 값을 p라고 했을 때, tree[p]에다가 해당 노드를 저장해준다. vector형태니까, push_back(해당 노드) 해주면 된다.
그럼 모든 노드에 대해서 바로 아래 자식 노드 리스트를 가지게 된다. 당연히, 자식이 없는 노드의 벡터는 비어있을 것이다.
그리고 삭제된 노드인지, 리프노드인지를 구별하기 위해 bool타입의 배열 leaf를 생성해서 false로 초기화 해주었다.
삭제할 노드를 입력받고, 해당 노드를 기준으로 dfs함수를 호출한다.
dfs 함수에서는 다음과 같이 동작한다. 입력 : tree, 삭제할 노드 node, leaf 로직 - 삭제할 노드의 자식 노드들을 순회한다. 즉 tree[node]를 순회한다. - 이 때 자식 노드를 num에 저장해두고, 자식의 자식들을 순회하기 위해 dfs를 호출하여 삭제할 노드로 num을 넘겨준다. -그리고 해당 노드에 대해 모두 순회했으면, tree[node]를 clear하여 모두 삭제해주고, 이는 삭제된 노드이므로 leaf[node]를 true로 변경해준다.
입력한 삭제 노드에 대해 위 로직을 따르고 나면, 이제 입력 값만을 부모에서 삭제해주면 된다.
부모를 찾기위해서 2중 for문을 통해 입력받은 값을 자식으로 갖는 노드가 있는지 순회하고, 일치하다면 해당 부모 노드의 배열에서 삭제하도록 한다. 그리고 순회를 즉시 멈춘다.
이제 삭제할 노드를 기점으로 모두 삭제되었으므로, tree배열을 순회하면서 leaf가 false이고(=삭제되지 않은노드), tree[i]의 size가 0인 노드를 카운트 하여 출력한다.
☑ 코드 전문
#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<int> tree[], int node, bool leaf[]) {
for (int i = 0; i < tree[node].size(); i++) {
int num = tree[node][i];
dfs(tree, num, leaf);
}
tree[node].clear();
leaf[node] = true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
vector<int> tree[50];
bool leaf[50] = {false};//false->true 개수만 세기
for (int i = 0; i < N; i++) {
int p;
cin >> p;
if (p == -1) continue;
else {
tree[p].push_back(i);
}
}
int node;
cin >> node;
dfs(tree, node, leaf);
bool br=false;
for (int i = 0; i < N; i++) {
for (auto it = tree[i].begin(); it != tree[i].end(); it++) {
if (*it==node) {
tree[i].erase(it);
br = true;
break;
}
}
if (br) break;
}
int answer = 0;
for (int i = 0; i < N; i++) {
if (!leaf[i]&&tree[i].size() == 0) answer++;
}
cout << answer;
return 0;
}
