백준 1068 - 트리

• 1068 - 트리

아주 기본적인 트리 구현 문제였다.
자료구조의 기본적인 감을 되찾기 위해 기본으로 돌아갔다.

가장 먼저, 어떤 방식으로 트리를 구현할 지가 처음엔 고민이었다.
이진 트리였다면 포인터 형식으로 구현해도 괜찮았을 것 같다.
하지만, 그런 제한이 따로 없으므로 단방향 인접 리스트로 구현하도록 했다.
단방향 인접 리스트는 자식을 여러 명 가질 수 있으며, 순회도 간편하다.

Adjacent List

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

int leaf_node = 0, deleted_node = 0;
void dfs(int curr, vector<bool>& visit, vector<vector<int>> tree) {
    if (visit[curr])
        return;
    visit[curr] = true;

    if (tree[curr].size() == 0)
        leaf_node++;
    if (tree[curr].size() == 1 && tree[curr][0] == deleted_node)
        leaf_node++;

    for (int i = 0; i < tree[curr].size(); i++) {
        if (tree[curr][i] != deleted_node)
            dfs(tree[curr][i], visit, tree);
    }
}

int main() {
    int nodes = 0, root = 0;
    cin >> nodes;

    vector<vector<int>> tree(nodes, vector<int>());
    vector<bool> visit(nodes, false);

    for (int i = 0; i < nodes; i++) {
        int parent = 0;
        cin >> parent;

        if (parent == -1)
            root = i;
        else
            tree[parent].push_back(i);
    }

    cin >> deleted_node;

    if (deleted_node == root)
        cout << 0;
    else {
        dfs(root, visit, tree);
        cout << leaf_node;
    }

    return 0;
}