[자료 구조] C++로 Tree depth 계산

#include <iostream>
#include <vector>
using namespace std;

#define endl '\n'

struct Node {
    int data;
    Node *parent;
    vector<Node *> childList;
    Node(int data, Node *parent) {
        this->data = data;
        this->parent = parent;
    }
};

class Tree {
public:
    Tree(int data);
    void insertNode(int parent, int data);
    void deleteNode(int data);
    void printParent(int data);
    void printChild(int data);
    void depth(int node1, int node2);

private:
    Node* root;
    vector<Node *> nodeList;

    int find(int data, vector<Node *> &list);
};

Tree::Tree(int data) {
    root = new Node(data, NULL);
    nodeList.push_back(root);
}

int Tree::find(int data, vector<Node *> &list) {
    // 노드가 없으면 -1
    for (int i = 0; i < list.size(); ++i) {
        if (list[i]->data == data)
            return i;
    }
    return -1;
}

void Tree::insertNode(int parent, int data) {
    if (find(data, nodeList) != -1) {
        cout << -1 << endl;
        return;
    }
    if (find(parent, nodeList) == -1) {
        cout << -1 << endl;
        return;
    }
    Node* parNode = nodeList[find(parent, nodeList)];
    Node* newNode = new Node(data, parNode);

    nodeList[find(parent, nodeList)]->childList.push_back(newNode);
    nodeList.push_back(newNode);
}

void Tree::deleteNode(int data) {
    if (find(data, nodeList) == -1) {
        cout << -1 << endl;
        return;
    }
    int idx = find(data, nodeList);
    Node *delNode = nodeList[idx];
    Node *parNode = delNode->parent;

    for (int i = 0; i < delNode->childList.size(); ++i) {
        delNode->childList[i]->parent = parNode;
        parNode->childList.push_back(delNode->childList[i]);
    }

    vector<Node *> &child = parNode->childList;
    child.erase(child.begin() + find(data, child));
    nodeList.erase(nodeList.begin() + idx);
    delete delNode;
}

void Tree::printParent(int data) {
    int idx = find(data, nodeList);
    if (find(data, nodeList) == -1) {
        cout << -1 << endl;
        return;
    }
    cout << nodeList[idx]->parent->data << endl;
}

void Tree::printChild(int data) {
    int idx = find(data, nodeList);
    if (idx == -1) {
        cout << -1 << endl;
        return;
    }

    vector<Node *> &child = nodeList[idx]->childList;
    if (child.size() == 0) {
        cout << -1 << endl;
        return;
    }

    for (int i = 0; i < child.size(); ++i) {
        cout << child[i]->data << ' ';
    }
    cout << endl;
}

void Tree::depth(int node1, int node2) {
    int fst = find(node1, nodeList);
    int snd = find(node2, nodeList);
    if (fst == -1 || snd == -1) {
        cout << -1 << endl;
        return;
    }
    int depth0 = 0;
    int depth1 = 0;

    Node *curNode1 = nodeList[fst];
    while (curNode1->parent != NULL) {
        curNode1 = curNode1->parent;
        ++depth0;
    }

    Node *curNode2 = nodeList[snd];
    while (curNode2->parent != NULL) {
        curNode2 = curNode2->parent;
        ++depth1;
    }

    cout << depth0 - depth1 << endl;
}

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

    Tree *tree = new Tree(1);

    int N, M;
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        tree->insertNode(x, y);
    }

    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        tree->depth(x, y);
    }

    return 0;
}