[BaekJoon][1068] 트리

BAEKJOON ONLINE JUDGE

1068 트리

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

1. 리프노트 세기

입력이 parent 니까 parent 로 나온 개수를 세면 자식 노드의 수를 알 수 있다.

값이 0인 것이 리프노드

2. 노드 제거

노드를 제거하였을 때 -> 부모노드가 리프노드가 될 수 있다.

 -> 자식노드들과 함께 사라질 수 있다.

살아있는 노드인지 확인하는 배열하나 더 추가하여 확인

 리프노드인데 부모가 사라지는 노드이면 같이 사라지면서 개수를 세지 않음

2번 틀림 -> 노드를 제거했을 때 부모노드가 리프노드가 될 수 있는 경우를 생각하지 못함

22분

#include <stdio.h>
 
int n;
int parent[55];
int node[55], check[55];
 
int erase(int no)
{
    if (no == -1)                return 0;
    if (check[no] == 1)    return 1;
    return check[no] = erase(parent[no]);
}
 
int solve(int rem)
{
    int i;
    int cnt = 0;
    
    check[rem] = 1;
    node[parent[rem]]--;
 
    for (i = 0; i < n; i++) {
        if (node[i] == 0) {
            if (erase(i) == 0) {
                cnt++;
            }
        }
    }
 
    return cnt;
}
 
int main()
{
    int i, p;
    int rem;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &p);
        parent[i] = p;
        if (p != -1) {
            node[p]++;
        }
    }
    scanf("%d", &rem);
 
    printf("%d\n", solve(rem));
 
    return 0;
}

풀이 2.

 구현은 안해봤지만 n이 작기 때문에 풀릴 것이다.

childCnt <- 자식 노드의 개수 배열

parent <- 부모 노드 저장한 배열

find(int nodeNum) <- 부모 노드 찾아가는 함수

모든 노드를 find 함수를 통해서 루트노드를 찾아가는데 중간에 삭제된 노드가 있으면 같이 삭제, 삭제하면서 자신이 삭제되면 그 부모의 자식 개수 감소

이렇게 모든 노드를 삭제하고 개수를 줄이고 하여 최종적으로 자식의 수가 0인 노드들을 카운트 하면 리프노드의 수를 셀 수 있다.