[백준] 1068번 트리

 

문제를 풀 때 예제에 자식이 2개가 최대인 예제 밖에 없어서 이진 트리인 줄 알고 문제를 풀었다가 질문게시판에 있는 반례에서 3개가 나오는 예시를 보고 다시 풀었다. node라는 구조체를 선언하고 node 내에 parent라는 부모 노드를 가리키는 node형 변수와 node형 벡터를 만들어 자식 노드들을 가리키게 했다.

 

 

처음으로 구조체 내에 벡터를 선언했는데 이번에 하면서 알게 된 사실이 있다. 구조체 내에 벡터를 사용할 때는 new를 사용하여 동적 할당을 해줘야한다. 그렇지 않으면 나중에 벡터에 push_back을 할 수 없다.

 

 

루트 노드가 무조건 첫 번째로 나온다는 보장이 없다. 따라서 입력한 숫자가 -1인 경우 루트 노드이므로 해당 노드의 num을 i로 설정하고 parent는 NULL로 설정한다. 입력한 숫자가 -1이 아닌 경우 루트 노드가 아니므로 해당 노드의 부모 노드를 설정하고 부모 노드의 벡터에 해당 노드를 push_back 한다.

 

 

지우고자 하는 노드가 루트 노드인 경우는 리프 노드가 0개 남으므로 바로 0을 출력 후 프로그램을 종료했다. 만약 루트 노드가 아닌 경우 해당 노드의 부모 노드의 벡터에서 해당 노드를 지워야 한다. 지우기 위해 해당 노드의 index를 구한다.

 

 

해당 노드를 지운후 트리의 리프 노드의 갯수를 구하는 함수를 호출한다.

 

 

해당 노드가 리프 노드인 경우 1을 리턴하고 리프 노드가 아닌 경우 해당 노드의 자식 노드의 리프 노드를 더해주는 형식으로 재귀를 사용하여 구한다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;


struct node {
    node* parent; // 부모 노드
    vector<node> *childs = new vector<node>(); // 자식 노드들
    int num; // 해당 노드의 번호
};

int N;

// 리프 노드의 개수를 구하는 함수
int leafCount(node& node) {
    int counts = 0;

    // 해당 노드가 리프 노드인 경우
    if (node.childs->empty())
        return 1;

    // 해당 노드의 자식 노드가 존재할 경우
    for (auto n : *node.childs) {
        counts += leafCount(n);
    }
    return counts;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<node> v(51); // 노드 저장 배열

    int root; // 루트 노드의 번호
    cin >> N;

    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        if (num == -1) { // 루트 노드인 경우
            root = i;
            v[root].num = root;
            v[root].parent = NULL;
        }
        else { // 루트 노드가 아닌 경우
            v[i].parent = &v[num];
            v[i].num = i;
            v[num].num = num;
            v[num].childs->push_back(v[i]);
        }
    }

    int num;
    cin >> num;
    
    // 지우고자 하는 노드가 루트 노드인 경우
    if (num == root) {
        cout << 0;
        return 0;
    }

    // 지우고자 하는 노드가 부모 노드의 몇번째 자식 노드인지 구한다.
    int index;
    vector<node> vv = *v[num].parent->childs;
    for (int i = 0; i < vv.size(); i++) {
        if (vv[i].num == num) {
            index = i;
            break;
        }
    }

    // 해당 노드를 부모 노드의 childs 배열에서 지운다.
    auto it = v[num].parent->childs->begin();
    v[num].parent->childs->erase(next(it, index));

    cout << leafCount(v[root]);


    return 0;
}