[백준] 트리(1068)

문제 링크 : [백준] 트리(1068)

문제 설명

트리 구조가 주어지고, 특정 노드 하나를 지웠을 때, 리프 노드의 수를 구하세요.

입력

N(노드의 수, 1 <= N <= 50)
P_i(부모 노드, 1 <= P_i <= N, 루트 노드는 -1)

5
-1 0 0 1 1
2

출력

2

카테고리

#트리 #BFS #DFS

시간 복잡도 상한

엄청 커도 됩니다.

해결 방법

1. 트리를 순회 하면서 리프 노드의 수를 세면 됩니다.
2. DFS든 BFS든 상관 없을 것 같습니다.
3. 삭제 된 노드를 만난 경우, 그 노드를 방문하지 않고 넘어가면 됩니다.
4. 여기까지만 하면 될 것 같지만, 몇가지 예외 사항이 있습니다.
   4-1. 삭제된 노드가 루트 노드인 경우, 모든 노드가 삭제되었기 때문에 0을 출력해야 합니다.
   4-2. 삭제된 노드의 부모 노드가 하나의 자식 노드(삭제된 노드)를 가진 경우, 그 노드의 자식이 모두 사라졌기 때문에, 그 노드가 다시 리프 노드가 됩니다.
5. 이 경우를 잘 처리하시면 됩니다.
6. 주변에서도 그렇고 질문에서도 이진트리로 문제를 푸신 분이 계시는데, 문제 어디에도 트리가 이진트리라는 언급은 없습니다.
7. 문제를 풀 때, 문제를 꼼꼼히 읽어보시고, 주어진 내용들로 논리적 오류 없이 조건들을 추론해야 합니다.
8. 주관적인 견해가 절대 들어가면 안됩니다.

시간복잡도

O(N)

코드

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int n,t,i,r,c,l;
vector<int>v[50];
queue<int>q;
int main(){
    scanf("%d",&n);
    for (;i<n;i++){
        scanf("%d",&t);
        if(t>=0)v[t].push_back(i);
        else r=i;
    }
    scanf("%d",&n);
    if(r==n){
        printf("0");
        return 0;
    }
    q.push(r);
    t=0;
    while(!q.empty()){
        c=q.front();q.pop();
        l=v[c].size();
        for(i=0;i<v[c].size();i++){
            if(v[c][i]==n)l--;
            else q.push(v[c][i]);
        }
        t+=!l;
    }
    printf("%d",t);
}