백준 1068번 트리 (C, C++)

 

DFS 깊이우선탐색 방식으로 문제를 해결하였습니다.

 

주의할 점은 DFS로 내려가면서 자식노드가 없는 리프노드의 경우와 삭제했을 때 생기는 리프노드의 경우를 구분해주어야합니다. 

삭제되는 위치에 따라 리프노드의 카운트가 변경되기 때문에,입력한 값의 노드가 삭제되었을 때 해당 DFS를 종료시켜주어야합니다.

 

리프노드의 카운트를 세는 경우는 왼쪽 자식노드와 오른쪽 자식노드가 없는 경우입니다.

이를 코드로 생각해보면 tree[node].size() == 0가 되겠습니다.

그리고 노드를 삭제했을 때 리프노드가 생기는 경우를 생각합니다.

 

다른 경우는 부모 노드가 tree[node].size()==1 왼쪽이든 오른쪽이든 자식노드를 하나만 갖고

그 자식노드가 삭제되었을 경우를 생각합니다. 

자식 노드를 한개를 갖고있는 부모노드의 자식을 삭제할 경우 부모 노드가 리프노드가 되지만,

2개를 갖고 있는 경우 리프노드가 되지않습니다.

 

#include<iostream>
#include<vector>

using namespace std;
int N;
int K;
int root;
int leaf = 0;
vector<int> tree[51];

int dfs(int node){
    if(node == K){
        return -1;
    }
    if(!tree[node].size()){
        leaf++;
        return 0;
    }
    for(int i = 0; i < tree[node].size(); i++){
        int temp = dfs(tree[node][i]);
        if(temp == -1 && tree[node].size() == 1){
            leaf++;
        }
    }
    return 0;
}
int main(){
    int num;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin>>num;
        if(num == -1){
            root = i;
        }else{
            tree[num].push_back(i);
        }
    }
    cin>>K;
    dfs(root);
    cout<<leaf;
    return 0;
}