6 Oct 2020

[백준] 1068 트리

[백준] 1068 트리

백준 1068


#include <iostream>
#include <vector>
#include <algorithm>
const int MAX = 51;
int n,node;
int deleteNode, parent[MAX], root;

// 핵심 로직
/*
매게 변수로 부모 인덱스가 들어간다. 
parent[i]의미 : i의 부모 
parent[i] == idx : i의 부모가 idx와 같은가 
num == 0 ? 1 : num : num이 0개라는 뜻은 자신이 리프노드라는 뜻이다.
*/

int numOfLeaf(int idx) {
    // 삭제 노드에 도달하면 0을 반환
    if (deleteNode == idx) {
    	return 0;
    }
    int num = 0;
    for (int i = 0; i < n; i++) {
    	if (parent[i] == idx) {
    		num += numOfLeaf(i);
    	}
    }
    return num == 0 ? 1 : num;
}

void input() {
    cin >> n;
    for (size_t i = 0; i < n; i++)
    {
    	cin >> node;
    	if (node == -1) {
    		root = i;
    	}
    	parent[i] = node;
    }
    cin >> deleteNode;
    cout << numOfLeaf(root);
}

void solution() {
    input();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
    solution();
    return 0;
}

Tags:
0 comments