[백준 1068] 트리

 

 

문제 : https://www.acmicpc.net/problem/1068

1068번: 트리

 

트리를 이용하는 문제이다.

구조체를 이용하여 노드가 가질 수 있는 child의 리스트들과 child의 수를 따로 담아줬다.

child 의 수를 따로 담아 준 것은 child 리스트에서 지우고자 하는 노드를 찾아서 지우는 것보다

바로 수를 출력하는것이 효율적이라 판단했기 때문이다.

 

(잠오는 상태에서 코드를 짜서 별로일 수 있다. 훨씬 좋은 코드가 인터넷에 있을거라 생각한다... ㅎ)

 

#include <iostream>
#include <vector>
using namespace std;

struct Node{
    int v;
    int childCnt = 0;
    Node* parent = NULL;
    vector<Node*> child;
};

Node* root;
Node* nodes[50];

int countLeaf(int v){
    int cnt = 0;
    if(nodes[v] == NULL) return 0;
    if(nodes[v]->childCnt == 0) return 1;
    for(int i = 0; i < nodes[v]->child.size(); i++){
        cnt += countLeaf(nodes[v]->child[i]->v);
    }
    return cnt;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<int> parLists(n);
    // 입력
    for(int i = 0; i < n; i++){
        cin >> parLists[i];
        nodes[i] = new Node;
        nodes[i]->v = i;
    }
    
    // 트리 생성
    for(int i = 0; i < n; i++){
        int curParent = parLists[i];
        if(curParent == -1){
            root = nodes[i];
        }else{
            nodes[i]->parent = nodes[curParent];
            nodes[curParent]->child.push_back(nodes[i]);
            nodes[curParent]->childCnt++;
        }
    }

    
    int wannaD;
    cin >> wannaD;
    
    // root 노드이면 0 출력 후 바로 종료.
    if(wannaD == root->v){
        cout << 0 << '\n';
        return 0;
    }
    
    nodes[wannaD]->child.clear();
    nodes[wannaD]->parent->childCnt -= 1;
    nodes[wannaD] = NULL;
    
    int cnt = countLeaf(root->v);
    cout << cnt << endl;
    
    return 0;
}