본인 풀이 (7/13)

#include<bits/stdc++.h>
using namespace std;
int n, temp, root, target;
vector<int> adj[54];

int dfs(int here){
    int ret = 0;
    int child = 0;

    for(int there : adj[here]){
        if(there == target){
            continue;
        }
        ret += dfs(there);
        child++;
    }

    if(child == 0 ){
        return 1;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> temp;

        if(temp == -1){
            root = i;
        }else{
            // temp노드에 자식노드 부착
            adj[temp].push_back(i);
        }
    }

    cin >> target;

    if(root == target){
        cout << 0 << "\n";
        return 0;
    }

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

    return 0;
}

1. 리프노드 체크 문제
2. int형 dfs 구현과, ret변수를 0으로 선언함으로써 노드의 수를 체크하는 것이 아닌 리프노드 여부만 체크할 수 있게 됨
3. 인접행렬 기반으로 구현. for문으로 각 노드를 순회하며 자식노드가 인접행렬 각 인덱스에 푸시된다.

복습 (7/17)

#include<bits/stdc++.h>
using namespace std;
int n, target, ret;
vector<int> adj[54];

int dfs(int here){
    int cnt = 0;

    if (here == target){
        return 0;
    }

    for (int there : adj[here]){
        cnt += dfs(there);
    }

    // 리프노드이면 1 리턴, 리프노드 아니면 가지치기 리턴
    if(cnt == 0){
        return 1;
    }else{
        return cnt;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int root;

    cin >> n;

    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;

        if(temp == -1){
            root = i;
        }else{
            adj[temp].push_back(i);
        }
    }

    cin >> target;

    ret = dfs(root);

    cout << ret << "\n";

    return 0;
}

1. 루트노드가 꼭 0번노드가 아닐 수 있다라는 점
2. 트리순회시 인접행렬로 풀이한다는 점
3. here-there 형태로 DFS순회를 진행한다는 점
4. 자기자신이 리프노드인 경우 1을 리턴한다. 그 외에는 쌓여온 노드 개수 전체를 리턴한다.
5. 삭제대상 노드인 경우 0을 리턴한다.