[백준 1068번] [트리] 트리

처음에 루트노드가 0으로 고정인줄 알고 실수하였다..

 

문제 자체는 되게 단순하다.

 

1. 트리를 구성하고

2. 특정 노드를 끊는다.(위 기준으로 끊으면 어차피 아래에 접근이 안된다.)

즉, parent node를 기준으로 해당 node를 끊어주기만 하면 된다.

 

다만, 가장 최상단 root node를 제거하는 경우는 따로 예외처리하도록 하자.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int arr[51][51];
int N;

int dfs(int start){
    bool check = true;
    int count = 0;
    for(int i = 0; i < N; i ++){
        if(arr[start][i] == 1){
            check = false;
            count += dfs(i);
        }
    }
    if(check == true) return 1;
    return count;
}

int main(void){
    fastio;
    memset(arr, 0, sizeof(arr));

    cin >> N;
    int start_node;

    for(int i = 0; i < N; i++){
        int temp;
        cin >> temp;
        if(temp == -1){
            start_node = i;
            continue;
        }
        arr[temp][i] = 1;
    }

    int erase;
    cin >> erase;

    if(erase == start_node){
        cout << 0 << "\n";
        return 0;
    }

    for(int i = 0; i < N; i++){
        arr[i][erase] = 0;
    }

    cout << dfs(start_node) << "\n";

    return 0;
}