알고리즘

[C++] 백준 1068번 : 트리

88dldl 2024. 2. 27. 00:34

https://www.acmicpc.net/problem/1068

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,d,root,leafsum=0;
vector<int> tree[50];
bool check[50];

void solve(int curnode)
{
    if(check[curnode]) return;
    check[curnode]=true;
    if(tree[curnode].size()==0 || (tree[curnode].size()==1 && tree[curnode][0]==d)){
        leafsum++;
    }
    for(int i=0;i<tree[curnode].size();i++){
        if(tree[curnode][i]!=d) solve(tree[curnode][i]);
    }
}

int main()
{
    cin>>n;
    int tmp;
    for(int i=0;i<n;i++){
        cin>>tmp;
        if(tmp==-1) root = i;
        else    tree[tmp].push_back(i); 
    }
    cin>>d;
    if(d==root) cout<<0;
    else {
        solve(root);
        cout<<leafsum;
    }
    return 0;
}