문제

문제 링크

문제 접근

  • 이 문제는 우선적으로 트리를 만들어주고 삭제할 노드를 받은 후에 루트에서부터 DFS로 뻗어가면서 삭제된 노드를 제외한 자식노드가 0개인 노드의 개수를 세주면 된다.

코드

#include <cstdio>
#include <vector>
using namespace std;
int n, par, root, del, ans;
vector<vector<int> > tree;

void find(int node){
    int child = 0;
    int cn = tree[node].size();
    for(int i = 0; i < cn; i++){
        int x = tree[node][i];
        if(x == del)continue;
        find(x); child++;
    }
    if(!child)ans++;
}

int main(){
    scanf("%d", &n);
    tree = vector<vector<int> >(n);
    for(int i = 0; i < n; i++){
        scanf("%d", &par);
        if(par == -1){
            root = i;
            continue;
        }
        tree[par].push_back(i);
    }
    scanf("%d", &del);
    if(root == del)printf("0");
    else{
        find(root);
        printf("%d", ans);
    }
}

느낀점

  • 비교적 쉬운 트리 문제였다!