[C++] 백준 - 1068 : 트리

문제 링크

1068번: 트리

 

 

풀이 )

  부모 노드에 대한 정보를 입력 받을 때, 반대로 부모 노드에 대한 자식 노드를 저장했다.

  cnt( )에서는 자식 노드를 타고가면서 리프 노드인 경우(자식 노드의 수가 0) 1을 더해주는 방식으로 총 리프 노드의 수를 구한다.

 

답이 될 수 있는 경우의 수를 3가지로 나눴다.

• 자르는 노드(이하 cut)가 루트인 경우: 남는 노드가 없으므로 0 출력
• cut의 sibling 노드가 있는 경우: cnt(root) - cnt(cut)
• cut의 sibling 노드가 없는 경우: cnt(root) - cnt(cut) + 1

 

cut의 sibling 노드가 있는 경우 cut을 자르게 되면 sibling 노드가 남기 때문에 root의 리프 노드 수에서 cut의 리프노드 수를 빼주면 된다.

반면 cut의 sibling 노드가 없는 경우 cut을 자르게 되면 cut의 부모 노드가 리프 노드가 되기 때문에 +1을 해주어야 한다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> childrenOf[50];
int parentOf[50];

int cnt(int node){
    int num = childrenOf[node].size();
    if(num == 0)
        return 1;
    int ret = 0;
    for(int i = 0; i < num; ++i){
        ret += cnt(childrenOf[node][i]);
    }
    return ret;
}

int main(void){
    int n;
    cin >> n;

    int root;
    for(int i = 0; i < n; ++i){
        int parent;
        cin >> parent;
        if(parent == -1)
            root = i;
        else{
            childrenOf[parent].push_back(i);
            parentOf[i] = parent;
        }
    }
    int cut;
    cin >> cut;

    if(cut == root){
        cout << 0;
        return 0;
    }
    int ans = cnt(root)-cnt(cut);
    if(childrenOf[parentOf[cut]].size() == 1)
        ans++;
    cout << ans << '\n';
}