[1068] 트리

문제 링크 : https://www.acmicpc.net/problem/1068

1068 - 트리

본문

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, $1$번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

입력

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

출력

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

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

풀이 방법은 여러 가지가 있을 수 있다. 노드의 개수가 50개로 매우 적은 편이고, 시간은 2초로 매우 널널한 편이라서, 정답을 찾아갈 수 있는 알고리즘도 크게 제약을 받지 않는다. 물론, 매우 비효율적으로 움직여도 가능하다.

입력으로 주어지는 정보는 노드의 자식들이 아닌 부모이므로, 루트부터 시작하여 트리를 만들어나가기는 쉽지 않다. 그래서, 트리 구조를 만들지 않고 답을 찾는 방법을 생각해보려했다. 모든 노드들의 부모 정보를 가지고 있으므로, 이를 이용하여 특정 노드가 리프 노드인지 확인하면 된다.

문제에서 원하는 조건인 “리프 노드”의 경우, 자식 노드가 0개인 노드를 의미한다. 즉, 어떤 노드 $x$에 대해 모든 노드가 $x$를 부모로 가지지 않을 때, 우리는 $x$를 리프 노드라고 할 수 있다. 이를 이용하여, 모든 노드에 대해서, 다른 모든 노드의 부모가 자신이 아닐 때, 그것을 리프 노드로 지정할 수 있다. 시간복잡도는 노드의 개수 $n$에 대해 $O(n^2)$.

다만, 문제의 조건에 삭제할 노드가 하나 존재한다. 노드 하나만 삭제되는 것이 아닌, 그 아래의 모든 노드가 삭제된다는 조건이 있다. 다행히도, 위와 같은 방법을 사용할 것이라면, 삭제되는 노드는 아예 없는 셈 치고 하던대로 진행하면 된다. 그 아래의 노드들의 경우, 삭제되는 노드가 이미 없는 상황이라면 그 아래를 탐색하지는 않으므로, 고려 대상이 아니다.

• 참고 알고리즘 : DFS 탐색

코드

사용 언어 : C

최종 수정일 : 2023 / 10 / 13

#include <stdio.h>

#define MAX_IDX 50
const int NO_PARENT = -1;

int parent[MAX_IDX];
int n;

int root;
int removed;
int result;

void dfs(int x) {
    int child = 0;
    for (int i = 0; i < n; ++i) {
        if (i != removed && parent[i] == x) {
            ++child;
            dfs(i);
        }
    }

    if (child == 0) {
        ++result;
    }
    return;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", parent + i);
        if (parent[i] == NO_PARENT) {
            root = i;
        }
    }
    scanf("%d", &removed);

    if (root != removed) {
        dfs(root);
    }

    printf("%d", result);
    return 0;
}