[백준] [C++] 트리 (tree)

1. 문제

 

1068번: 트리 (acmicpc.net)

1068번: 트리

 

 

2. 풀이

트리의 리프노드는 부모 노드말고 연결점이 없다.

 

따라서 처음 트리를 인접리스트 형태로 데이터를 받은 후

 

리프노드를 set에 담은 뒤

 

재귀적으로 제거하는 노드에 딸린것들을 모두 제거하고

 

제거하는 노드 중 리프 노드인것을 set 에 지워버리면 

 

남은 리프 노드의 개수를 알아낼 수 있다.

(제거하는 노드의 부모가 리프 노드가 될 수 있으므로 예외처리 해줘야한다.)

 

 

 

#include <iostream>
#include <vector>
#include <utility>
#include <set>
 
using namespace std;
 
void recursionDelete(vector<vector<int> >& tree, set<int>& leap, int d) {
    if(tree[d].empty()) {
        leap.erase(d);
        return;
    }
    for(int i = 0; i < tree[d].size(); i++) {
        recursionDelete(tree, leap, tree[d][i]);
    }
    tree[d].clear();
}
 
int deleteTree(vector<vector<int> >& tree, int d) {
    set<int> leap;
    int size = tree.size();
    for(int i = 1; i < size; i++) {
        if(tree[i].empty()) {
            leap.insert(i);
        }
    }
    recursionDelete(tree, leap, d+1);
    return leap.size();
}
 
//tree => 0 is root
int main() {
    int n = 0, d = 0, answer = 0;
    cin>>n;
    vector<int> parent(n, 0);
    vector<vector<int> > tree(n+1);
    for(int i = 0; i < n; i++) {
        cin>>parent[i];
        tree[parent[i] + 1].push_back(i+1);
    }
    cin>>d;
    answer = deleteTree(tree, d);
    if(tree[parent[d]+1].size() == 1 && parent[d] != -1) {
        answer++;
    }
    cout<<answer<<"\n";
}