1068번 백준(Baekjoon)

<문제>

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

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

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 제거한다고 하면, 다음과 같이 된다.

이제 리프 노드의 개수는 1개이다.

<정답 코드>

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> v[51];
vector<int> parent;
queue<int> q;
int N, m, c, cnt;
 
void bfs()
{
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        int size = v[front].size();
        if (size == 0)
            cnt++;
        else
            for (int i = 0; i < size; i++)
                q.push(v[front][i]);
    }
}
 
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> m;
        if (m != -1)
            v[m].push_back(i);
        else
            parent.push_back(i);
    }
    cin >> c;
    
    for (vector<int>::iterator iter = parent.begin(); iter != parent.end(); iter++) {
        if (*iter == c) {
            parent.erase(iter);
            break;
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (vector<int>::iterator iter = v[i].begin(); iter != v[i].end(); iter++)
            if (*iter == c) {
                v[i].erase(iter);
                break;
            }
                
    }
    int size = parent.size();
    for (int i = 0; i < size; i++) {
        q.push(parent[i]);
        bfs();
    }
    cout << cnt;
    return 0;
}