[ 백준 BOJ ] 1068번 - 트리 (C++)

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

 

생각 흐름

1. 부모 노드를 저장하는 방식으로 -1 0 1 있을 때 2번 노드에 0과 1이 저장되는 것과 같이 노드의 모든 부모를 저장하기로 했다.
   • 3 1 1 4 -1인 경우에는 1번과 2번 노드에서 4번 노드에 대한 정보가 안 들어가는 문제 확인
2. 노드에 부모 노드 대신, 자식 노드를 모두 저장하기로 결정
   • 자식을 지웠을 때 부모 노드가 리프 노드가 되었을 때의 경우를 고려하지 못해 77%에서 실패
   • 자식이 지워야 하는지 확인 후, 지워야 하는 자식일 시엔 부모 노드의 자식 수를 세어 1인 경우엔 부모 노드가 자식이 되므로 answer++ 해주고 return 해주는 방식으로 변경
   • 성공

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int N;
vector<int> v[50];
int numToDelete;
int answer;

void travel(int node){
    if(v[node].empty()) answer++;
    
    for(int i = 0 ; i<v[node].size(); i++){
        if(v[node][i]==numToDelete){
            if(v[node].size()==1){
                answer++;
                return;
            }
            continue;
        }
        travel(v[node][i]);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    
    int root = -1;
    
    for(int i = 0; i<N; i++){
        int tmp;
        cin>>tmp;
        
        if(tmp==-1){
            root = i;
            
            continue;
        }
        
        v[tmp].push_back(i);
    }
    
    cin>>numToDelete;

    if(numToDelete == root){
        cout<<0<<endl;
        return 0;
    }
    
    travel(root);
    
    cout<<answer<<endl;
    
    return 0;
}