[백준/C++] 1068번 트리

https://www.acmicpc.net/problem/1068

1068번: 트리

간단한 트리 + dfs 문제이다.

그런데 이 문제는 문제를 잘 읽어야한다. 이진트리도 아니며, 입력으로는 노드가 순서대로 주어지는 것이 아니라 노드의 부모가 주어진다.    그리고 꼭 0번 노드(첫 입력)가 root노드인 것은 아니다! -1(부모가 없는 경우)이 입력으로 들어올 때 해당 노드가 트리의 root이다. 

예제 1번이 문제의 그림과 동일하므로 천천히 비교해보시길 바란다.

우선 트리를 입력받은 뒤, 부모부터 dfs를 시작한다. 입력은 2차원 벡터를 이용해 부모-자식을 표현한다.

만약 현재 노드가 지워져야할 노드면 -1을 반환한다. (추후에 또 쓰일 예정)

만약 자식이 없다면 leaf 노드이므로 답을 카운트해주고 재귀를 종료한다.

for문은 node가 가진 자식의 수만큼 탐색을 하는데, 입력받을 때 부모에 먼저 들어간 놈이 왼쪽 자식이다.

그러므로 왼쪽 자식부터 쭉 dfs를 돌게 되고, 만약 자식이 지워질 노드라 -1를 반환받게 되었다고 가정하고 그것이 유일한 자식이면 부모가 leaf가 되므로 답을 카운트해준다!

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,del,root,ans;
vector<int> tree[51];

int dfs(int node) {
    if (node == del) return -1;
    if (tree[node].empty()) { // 자식이 없으면 leaf
        ans++;
        return 0 ;
    }
    for (int i = 0; i < tree[node].size(); i++) {
        int tmp = dfs(tree[node][i]); // dfs 탐색
        if (tmp == -1 && tree[node].size() == 1) // 자식 노드가 삭제될 노드이고 자식이 하나라면 부모가 leaf가 된다.
            ans++;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if (num == -1)
            root = i;
        else
            tree[num].push_back(i);
    }
    cin >> del;
    dfs(root);

    cout << ans;
    return 0;
}