1068 : 트리 - DFS, 트리

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

1068번: 트리

문제요약

트리 구조에서 한 노드를 지웠을 때 리프노드의 개수를 구하라.

 

난이도

Gold 5

---

//내 코드
#include <bits/stdc++.h>
using namespace std;

int n, a[52], k, ret;
vector<int> adj[52];

bool b[52];

void cut(int node)
{
    b[node] = false;

    for (int s : adj[node])
    {
        cut(s);
    }
}

int main()
{

    // 입력 받기
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] != -1)
            adj[a[i]].push_back(i);
        b[i] = true;
    }

    cin >> k;

    if (a[k] == -1)
    {
        ret = 0;
    }
    // 노드 삭제
    else
    {
        cut(k);

        for (int i = 0; i < n; i++)
        {
            if (b[i] == false)
                continue;
            if (adj[i].size() == 0)
                ret++;
            else
            {
                bool flag = 1;
                for (int j : adj[i])
                {
                    if (b[j] == true)
                        flag = 0;
                }
                if (flag)
                    ret++;
            }
        }
    }

    cout << ret;
}

#include <bits/stdc++.h>
using namespace std;
// there가 없고 here만 있는 경우

int n, r, temp, root;
vector<int> adj[54];

int dfs(int here)   // 리프노드의 수를 구하는 함수
{
    int ret = 0;
    int child = 0;
    for (int there : adj[here])
    {
        if (there == r)
            continue;
        ret += dfs(there);
        child++;
    }
    if (child == 0)
        return 1;
    return ret;
}

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

    cin >> n;

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

    cin >> r;

    if (r == root)
    {
        cout << 0 << "\n";
        return 0;
    }
    cout << dfs(root) << "\n";
    return 0;
}