[1068] 트리

문제 출처 : https://www.acmicpc.net/problem/1068

분류 : 트리

백준 1068 트리

트리의 노드를 삭제시 남은 리프 노드의 갯수를 구하라

---

구현 포인트

1) 트리를 간단하게 구현(배열로)

2) Bottom-up으로 리프의 갯수를 파악한다.

우선 첫번째로 풀었던 방식은 각 노드마다 각 노드가 root인 sub-tree의 리프노드 갯수를 가지고 있게 한뒤

노드가 삭제되면 전체 리프노드 갯수에서 삭제된 리프노드의 갯수를 삭제하도록 했다.

이렇게 생각하면 고려해야 하는 부분이 더 생긴다.

위와 같이 4번노드를 삭제 할 때 자식 노드가 1개로 이어진 경우 위와 같은 논리는 문제가 생긴다.

이런 경우를 고려하여 답을 찾도록 추가적으로 구현을 해주어야 했다.

#include<cstdio>
#include<vector>
using namespace std;
int main() {
    int n, erase, root;
    scanf("%d", &n);
    vector<int> num_node(n, 0);
    vector<int> parent(n);
    vector<int> degree(n, 0);
    for (int i = 0; i < n; i++) {
        int p;
        scanf("%d", &p);
        parent[i] = p;
        if (p != -1){
            num_node[p]++;
        }
        else root = i;
    }
    for (int i = 0; i < n; i++) {
        if (num_node[i] == 0) {
            degree[i] = 1;
            int cur = i;
            int p = parent[i];
            while (p!=-1) {
                degree[p] += degree[i];
                cur = p;
                p = parent[cur];
            }
        }
    }
    scanf("%d", &erase);
    if (degree[parent[erase]] == degree[erase]) {
        printf("%d\n", degree[root] - degree[erase] + 1);
    }else {
        printf("%d\n", degree[root] - degree[erase]);
    }
}

그런데 사실 트리를 배열로 구현하면 좀 더 깔끔한 방법이 있을 것 같다.

트리를 배열로 구현하면서 각 노드의 자식 노드의 갯수를 가지고 있다면

우리는 리프노드를 판별 할 수 있다.

즉, 리프노드를 판별 하여 리프노드 별로 트리를 거슬러 올라가 root에 도달하는 경우를

세어주면 답이 된다는 사실을 알 수 있다.

그렇게 되면 첫번째 방식에서 생기던 문제상황을 고려하지 않아도 해결이 됨을 알 수 있다.

(물론 여기서는 root를 제거할 때에 유의해야 한다.)

코드는 아래와 같다.

#include<cstdio>
#include<vector>
using namespace std;
int main() {
    int n, erase, root, answer = 0;
    scanf("%d", &n);
    vector<int> num_node(n, 0);
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        int p;
        scanf("%d", &p);
        parent[i] = p;
        if (p != -1){
            num_node[p]++;
        }
        else root = i;
    }
    scanf("%d", &erase);
    if(erase!=root)
        num_node[parent[erase]]--;
    else root = -2;
    parent[erase] = -1;
    for (int i = 0; i < n; i++) {
        if (!num_node[i]) {
            int cur = i;
            while (cur!=-1) {
                if (parent[cur] == root) {
                    answer++;
                    break;
                }
                cur = parent[cur];
            }
        }
    }
    printf("%d\n", answer);
}