[백준] 트리(1068)

문제
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

 

예제 입력

5

-1 0 0 1 1

2

 

예제 출력

2

---

이 문제의 질문 게시판을 가보면 난항을 겪고 문제에 불만을 가지는 사람이 일부 보인다. 동의하는 부분이 있긴 하지만, 트리 개념이 명확하지 않아서, 알고리즘 문제를 많이 다뤄보지 않아 겪는 일 같다. 문제에 '이진'이라는 말이 없으므로 이진 트리가 아니며 '트리'이기 때문에 루트는 하나다. 루트가 여러 개면 '포레스트', '숲'이라고 해야 한다.

 

리프 노트만 새면 되니까 디테일하게 트리를 구성하지 않아도 된다. 상용화할 서비스에 들어갈 자료구조를 만드는 게 아니기 때문에 구조를 활용하여 문제를 어떻게 해야 쉽게 풀지 고민하는 게 중요한 것 같다. 나도 아직 갈 길이 멀다. 루트부터 차례대로 탐색한다.

 

깊이 우선 탐색으로 진행되며 시간 복잡도는 O(n)이다. 노드는 벡터의 배열로 선언됐기 때문에 이차원 배열이다. 해당 노드가(now)가 삭제할 노드(delete_node)라면 바로 함수를 리턴하며 그렇지 않을 때는 경우의 수를 따진다. 자식이 없으면 ++answer를 해준다. 자식이 하나인데 delete_node라면 역시 ++answer. 자식이 하나인데 delete_node가 아니라면 다시 탐색을 들어간다. 자식이 두 개 이상일 때는 순차적으로 깊이 탐색을 해 위의 과정을 반복한다.

#pragma warning(disable:6031)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
std::vector<int> node[50];
int count, delete_node;
void CountLeafNode(int& now)
{
    if (now == delete_node) return;
    size_t size = node[now].size();
    switch (size)
    {
    case 0:
        ++count;
        break;
    case 1:
        if (node[now][0] == delete_node) ++count;
        else CountLeafNode(node[now][0]);
        break;
    default:
        for (int i = 0; i < size; ++i)
            CountLeafNode(node[now][i]);
        break;
    }
}
 
void ProblemSolved()
{
    int parent, N, root;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &parent);
        if (parent == -1)
            root = i;
        else
            node[parent].push_back(i);
    }
    scanf("%d", &delete_node);
    CountLeafNode(root);
    printf("%d\n", count);
}
int main()
{
    ProblemSolved();
    return 0;
}