문제

  • 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

  • 첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

예제

예제 입력
5
-1 0 0 1 1
2

예제 출력
2

접근

  • 트리를 만드는 것은 기본이고, 제거되는 노드를 어떻게 처리 할까 고민을 했다.
    • BFS를 통해 트리를 탐색할 예정이었으므로 제거되는 노드가 나오면 건너뛰고 탐색을 계속 진행하는 알고리즘을 생각했다.
  • 리프 노드의 count는 어떻게 할 것인가?

내가 생각한 풀이

  • 접근에서 생각했던 것과 같은 방법으로 BFS를 실행한다.
  • 더 이상 push가 진행되지 않는다면 leaf 노드이므로 count를 해준다.

미처 생각하지 못했던것

  • root 노드가 제거되면 무조건 0이 되는게 맞는데 이 쉬운걸 깜빡하고 있었다… 다른 로직은 바로 맞게 짰으나 5번인가 틀리고 성공…ㅠㅠ
  • 웃긴건 root 노드를 제거하는 TC를 스스로 만들어놓고도 간과하고 넘어갔다 ㅋㅋㅋ

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(void){
  int N, del, root, r=0;
  vector<int> v[51];
  cin>>N;
  for(int i = 0 ;i<N;i++){
    int t;
    cin>>t;
    if(t != -1){v[t].push_back(i);v[i].push_back(t);}
    else root = i;
  }
  cin>>del;
  if(N==1 || del==root){ //root가 삭제될 경우 무조건 0이 되야 한다는 쉬운 사실을 왜 깜빡하고 있었을까...? 매우 멍청쓰했당 ㅠ
    cout<<0;
    return 0;
  }
  queue<int> q;
  bool chk[51] = {0, };
  q.push(root);
  chk[root] = 1;
  while(!q.empty()){
    int t = q.front(), flag = 0;
    q.pop();
    for(int i = 0 ;i<v[t].size();i++){
      if(chk[v[t][i]] == 0 && v[t][i] != del){
        q.push(v[t][i]);
        chk[v[t][i]] = 1;
        flag = 1;
      }
    }
    if(flag == 0){r++;}
  }
  cout<<r;
  return 0;
}