[백준/c++] 1068번: 트리

 

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

1068번: 트리

 

노드 하나를 지울 것이다. 남은 트리에서 리프 노드의 개수를 구하자.

노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

 

루트 노드를 구하고 (m==-1 라면 root node) DFS를 root부터 시작해준다.

DFS를 사용하면 서브 노드 끝까지 내려가게 되는데, child를 0으로 초기화하고 해당 노드의 서브 트리를 돌고, 만약 자식 노드가 하나도 없다면 1을 리턴하도록 한다. (자신이 leaf node 이므로)

 

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

vector<int> tree[50];
int del;

int RemoveNode(int x){ //DFS
    int child = 0;
    
    for(auto ch : tree[x]){ //x에 연결된 노드(child, 자식노드) 순환 - DFS라서 서브트리를 쭉 깊게 들어간다
        if(ch == del) continue;  //자식노드가 지울 노드라면 패스
        child += RemoveNode(ch); //지울 노드가 아니면 해당 노드의 서브트리의 리프노드 개수 카운팅
    }
    
    if(child) return child; //leaf node 가 아닌 경우 (child != 0인 경우)
    else      return 1;     //leaf node 라면 1 리턴
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, root = 0;
    cin >> n;
    for(int i=0; i<n; i++){
        int m;
        cin >> m;
        if(m == -1) root = i; //root 체크
        else        tree[m].push_back(i); //부모 노드 m, 자식 노드 i번
    }
    cin >> del; //지울 노드 번호
    
    if(root != del) cout << RemoveNode(root) << '\n'; //루트부터 DFS 탐색
    else            cout << 0 << '\n'; //루트를 지울 경우, 0 출력
    return 0;
}