백준 1068번: 트리 C++코드(트리, BFS)

#include <iostream>
#include <queue>
using namespace std;

int parents[51];
int n;
int d;

int bfs(){
    queue <int> qq;
    int state = 0;
    int cnt = 0;
    for(int i=0; i<n; i++){
        if(parents[i] == -1){
            qq.push(i);
            if(i == d){
                return 0;
            }
        }
    }
    while(!qq.empty()){
        int now = qq.front();
        qq.pop();
        state = 0;
        for(int i=0; i<n; i++){
            if(parents[i] == now){
                if(i != d){
                    qq.push(i);
                    state = 1;
                }
            }
        }
        if(state == 0){
            cnt++;
        }
        
    }
    return cnt;
}

int main() {
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> parents[i];

    }
    cin >> d;
    cout << bfs();
}

알고리즘 분류는 깊이 우선 탐색이긴하나 너비 우선 탐색으로 해결하였다. 

트리를 parents라는 배열을 만들어서 i번째 노드는 parents[i]에서 부모노드를 가르키도록 해서 트리를 구현했다. 이후 bfs로 타고 들어가면서 그 밑에 들어갈 자식 노드가 없다면 리프 노드이므로 cnt를 증가시켜주는 식으로 구현했다.