[3일차][2진트리] 부모의 갯수 자식 갯수 세기

- 문제 설명

주어진 엣지(부모-자식)로 트리를 구성하여 해당 노드의 부모 갯수, 자식갯수를 출력

2

1                5

6

4

위와 같을때 1의 부모 갯수는 1개 자식갯수는 2개기 때문에 1, 2를 출력하면 된다.

- 입력

1 // 테스트 케이스

5 1 //엣지 갯수 주어진 노드

2 1 1 6 6 4 2 5 5 3

- 출력

#1 1 2 // 테스트케이스, 부모갯수, 자식 갯수

- 입력 예시

3
5 1
2 1 2 5 1 6 5 3 6 4 
5 1
2 6 6 4 6 5 4 1 5 3 
10 5
7 6 7 4 6 9 4 11 9 5 11 8 5 3 5 2 8 1 8 10 

- 출력 예시

#1 1 2
#2 3 0
#3 3 2

- 코드

#include "stdio.h"

int findParentCount(int node);

void findChildCount(int node);

int ch1[1002]; // 왼쪽 자식 노드

int ch2[1002]; // 오른쪽 자식 노드

int par[1002]; // 부모

int childCount; // 자식 카운트

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        int edge;

        int node;

        scanf("%d %d",&edge, &node);

        for(int i=0;i<1002;i++) // 초기화

        {

            ch1[i] = 0;

            ch2[i] = 0;

            par[i] = 0;

        }

        for(int i=0; i < edge; i++) // 입력값 받기

        {

            int n1,n2;

            scanf("%d %d",&n1,&n2);

            if(ch1[n1] == 0) // 자식 노드 채우기

                ch1[n1] = n2;

            else

                ch2[n1] = n2;

            par[n2] = n1; // 부모 노드 채우기

        }

        int parentCount = findParentCount(node);

        childCount = 0;

        findChildCount(node);

        printf("#%d %d %d\n",tc,parentCount,childCount-1); // 1을 빼주는 이유는 자기까지 셋기때문에

        

    }

    return 0;

}

int findParentCount(int node) // 조상 찾기

{

    int count = 0;

    while (par[node] != 0) // 현재 노드의 조상이 있다면

    {

        node = par[node]; // 현재 노드를 조상노드로 바꾸고

        count++; // 카운트 증가

    }

    return count; // 끝나고 카운트 반환

}

void findChildCount(int node) // 자식 찾기

{

    if (node != 0) // 현재 노드가 0이 아니면

    {

        childCount++; // 카운트 증가

        findChildCount(ch1[node]); // 왼쪽 자식 노드

        findChildCount(ch2[node]); // 오른쪽 자식 노드

    }

}