Tree에서 특정 노드를 삭제했을때 리프 노드의 개수를 구하는 문제이다.

DFS를 통해 트리 순회가 가능하므로, 루트 노드에서부터 시작해서 트리를 순회한며, 삭제하는 노드를 만나면 인접 리스트 순회 과정에서 continue로 무시해주면 된다.

이게 기본적인 컨셉이고,,구현 과정에 몇 가지 주의점이 존재한다.

(1) 삭제된 노드로 인해서 새롭게 리프노드가 되는 노드들이 존재한다
-> child 변수를 통해 continue처리되는 애들을 제외한 각 노드의 자식 노드 갯수를 카운트한다. 만약 인접리스트 순회가 끝나고도 child가 0이면 리프노드이므로 1을 return해준다.

(2) 루트 노드가 항상 0번 노드인것은 아니다.

문제 어디에도 루트 노드가 항상 0번 노드라는 말은 존재하지 않는다. 따라서 문제에 나와있는대로 -1을 입력받은 경우, 해당 번호를 루트노드로 인식하는 것이 적절하다.

(3) 카운트를 누적해야한다.
이런류의 그래프 탐색을 통해 카운트하는 문제는 int형 dfs를 설계하여 지역 변수 cnt를 두고 cnt+=dfs(here)로 매번 재귀호출을 수행하면 편리하게 카운트할 수 있다.

(4) 트리 순회에는 visited[] 배열이 필요없다. root부터 tree 순회를 시작하면 아래로 점점 내려가므로 같은 노드를 절대로 반복할 수 없다. 그래서 visited[]배열이 따로 필요없다.

(5) 시간복잡도는 트리 순회이므로 평균 O(n)이다.

1. 풀이 (1)

#include <bits/stdc++.h>

using namespace std;
vector<int> a[51];
int del;
int dfs(int from) {
    int cnt=0;
    int child = 0;
    for(int here: a[from]) {
        if(here == del) continue;
        child++;
        cnt+=dfs(here);
    }
    if(child==0) return 1;
    return cnt;
}
int main() {
    int n,in,root;
    cin >> n; //5
    for(int i=0;i<n;i++) {
        cin >> in; //5
        if (in == -1) { root = i; continue; } 
        a[in].push_back(i);
    }
    cin >> del;
    if(del==root) {
        cout << 0; return 0;
    }
    cout << dfs(root);
    return 0;
}

2. 오답 노트

(1) 반례를 충분히 생각해보지 못했다.

삭제된 노드로 인해서 새롭게 리프노드가 되는 노드가 존재한다. 그러나 이번에도 공개된 테케만 해보고, 히든 테케에 대해서 생각해보지 못했다. 히든 테케를 꼭꼭꼭꼭 생각해보자.....

(2) 루트 노드가 항상 0번 노드인것은 아니다.

공개 테케만보고 루트 노드가 항상 0이라 생각했다. 문제에서도 -1이 루트노드라 했으므로, 문제에 입각해서 문제를 해석할때 내 주관을 담지않도록 노력해야겠다.

(3) 트리 순회에는 visited[] 배열이 필요없다.

트리를 dfs로 순회하면 항상 아래 방햐응로 내려가므로 절대 같은 노드를 재반복할 일이 없다. 따라서 노드 방문 정보를 저장하기위한 visited[] 배열이 필요없다.