BOJ(백준) 1068 - 트리

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

---

자료구조(트리), 리프노드, 차수, 트리 방향성

루트 있는 트리가 주어지고, 각 노드들의 부모노드가 주어진다. 어떤 한 노드를 제거 했을 때, 남는 리프노드(단말노드)의 개수를 구하는 프로그램을 작성하라.

---

시간복잡도 : O(N)

N은 트리 노드의 개수

---

점검해봐야 할 부분

-루트가 있는 트리의 방향성

-리프 노드의 성질

---

https://github.com/jongwuner/Algorithm/blob/master/BOJ/1068.cpp

#include<cstdio>
int p[50], a, c[50];
int main(){
    int n, d;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", p + i);
        if(p[i]>=0) c[p[i]]++;
    }
    scanf("%d", &d);
    c[p[d]]--;
    for (int i = 0; i < n; i++){
        if (c[i]) continue;
        int j = i;
        while (j != -1){
            if (j == d) break;
            j = p[j];
        }
        a += j == -1;
    }
    printf("%d\n", a);
    return 0;
}