bool isLeaf=true
➡️ 현재 노드가 리프노드라고 전제하고 시작. 현재 노드를 부모 노드로 가지는 노드가 존재하지 않는다면 이 값이 false
가 되지 않고 리프노드로 판정될 것isLeaf
값이 false
로 변하지 않으면서 현재 노드가 리프노드로 판정될 것isLeaf
가 true
이면 현재 노드를 리프노드로 count
삭제될 노드를 따로 표시해줄 필요없이 방문표시 만으로 리프노드를 탐색해가면서 삭제될 노드를 제외시켜줌
➡️ 입력 받은 삭제노드를 visited
처리 해주고 탐색을 시작하면 해당 노드를 부모로 가지는 노드를 탐색할 수 없으므로 삭제 노드의 모든 자식 노드를 탐색하지 않게 됨
➡️ 현재 노드를 부모 노드로 가지는 vector 의 size 가 0인지 판단해주지 않아도 현재 노드를 부모 노드로 가지는 값이 하나도 없다면 탐색조차 할 수 없기 때문에 탐색 이전에 isLeaf
같은 bool 형 변수를 탐색할 자식 노드가 있는 경우에만 바꿔주는 방식으로 풀이
#include <iostream>
#include <vector>
using namespace std;
vector<int> root[50];
int cnt=0;
bool visited[51];
void dfs(int cur) {
if(visited[cur]) return;
visited[cur]=true;
bool isLeaf=true;
for(int i=0;i<root[cur].size();i++) {
int next=root[cur][i];
if(!visited[next]) {
dfs(next);
isLeaf=false;
}
}
if(isLeaf) cnt++;
}
int main() {
int n,s=0,d;
cin >> n;
for(int i=0;i<n;i++) {
int k;
cin >> k;
if(k==-1) s=i;
else root[k].push_back(i);
}
cin >> d;
visited[d]=true;
dfs(s);
cout << cnt;
}