[Algorithm]Baekjoon 1068번 : 트리

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

1068번: 트리

 
int n, input;
int rootNode = 0;
int deleteNode = 0;
int answer = 0;
vector<vector<int>> graph(51);
 
 
void DFS(int node, int parentNode)
{
    if (node == deleteNode)
    {
        if (parentNode != -1 && graph[parentNode].size() - 1 == 0)
        {
            ++answer;
        }
        return;
    }
 
    if (graph[node].size() == 0)
    {
        ++answer;
        return;
    }
 
    for (int i = 0; i < graph[node].size(); ++i)
    {
        DFS(graph[node][i],node);
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
 
        if (input == -1)
        {
            rootNode = i;
            continue;
        }
 
        graph[input].push_back(i);
    }
 
    cin >> deleteNode;
 
    DFS(rootNode, -1);
    cout << answer;
}

 

주어진대로 구현하면서, 한가지만 유의하면 된다.

특정노드를 삭제하면 부모노드의 자식개수는 1개 줄어드는셈이니, 그거에 따른 처리만 추가해주면 된다.