[BOJ/C++] 1068: 트리

🏅 Gold 5

✏️ 1차 솔루션

1. 삭제할 노드와 그 자식 노드를 삭제되었다고 표시하기 위해 각 노드의 루트노드를 99로 갱신
2. 루트 노드부터 리프노드 탐색 시작
   1) 왼쪽 자식 노드, 오른쪽 자식 노드 모두 없으면 리프노드로 판단하고 1 return해서 리프노드로 count해줌
   2) 왼쪽 노드, 오른쪽 노드 존재하면 계속 이어서 탐색해서 그 결과값 더해서 return

🚨 1차 trouble

1. 이진트리를 전제로 하지 않기 때문에 자식이 2개를 넘어갈 수 있음
2. 0 번째 수가 무조건 루트노드인 것이 아님

✏️ 최종 솔루션

1. 부모 노드를 기준으로 같은 부모를 갖는 것끼리 저장되도록 2차원 vector 구성
2. 방문처리하면서 리프노드 탐색
   1) 주어진 삭제노드부터 방문 처리
   2) 현재 노드가 방문한 노드라면 삭제 처리
   3) bool isLeaf=true ➡️ 현재 노드가 리프노드라고 전제하고 시작. 현재 노드를 부모 노드로 가지는 노드가 존재하지 않는다면 이 값이 false 가 되지 않고 리프노드로 판정될 것
   4) 현재 노드의 자식 노드 탐색하면서 방문하지 않은 노드가 있다면 재귀로 탐색 ➡️ 이 경우에도 자식 노드를 모두 방문했다면 isLeaf 값이 false 로 변하지 않으면서 현재 노드가 리프노드로 판정될 것
   5) 현재 노드에서 탐색을 완료한 이후에도 isLeaf 가 true 이면 현재 노드를 리프노드로 count

📌 self feedback

삭제될 노드를 따로 표시해줄 필요없이 방문표시 만으로 리프노드를 탐색해가면서 삭제될 노드를 제외시켜줌
➡️ 입력 받은 삭제노드를 visited 처리 해주고 탐색을 시작하면 해당 노드를 부모로 가지는 노드를 탐색할 수 없으므로 삭제 노드의 모든 자식 노드를 탐색하지 않게 됨
➡️ 현재 노드를 부모 노드로 가지는 vector 의 size 가 0인지 판단해주지 않아도 현재 노드를 부모 노드로 가지는 값이 하나도 없다면 탐색조차 할 수 없기 때문에 탐색 이전에 isLeaf 같은 bool 형 변수를 탐색할 자식 노드가 있는 경우에만 바꿔주는 방식으로 풀이

✏️ 최종 code

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

vector<int> root[50];
int cnt=0;
bool visited[51];

void dfs(int cur) {
    if(visited[cur]) return;
    visited[cur]=true;
    bool isLeaf=true;
    for(int i=0;i<root[cur].size();i++) {
        int next=root[cur][i];
        if(!visited[next]) {
            dfs(next);
            isLeaf=false;
        }
        
    }
    if(isLeaf) cnt++;
}

int main() {
    int n,s=0,d;
    cin >> n;
   
    for(int i=0;i<n;i++) {
        int k;
        cin >> k;
        if(k==-1) s=i;
        else root[k].push_back(i);
    }
    
    cin >> d;
    visited[d]=true;
    
    dfs(s);
    
    cout << cnt;
}