[PS] 백준 1068 트리 (c++)

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

1068번: 트리

트리(tree)란 ? 

그래프(Graph)의 일종으로, 한 노드에서 시작해 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프입니다. 최상단 노드를 루트노드, 자식이 없는 노드를 리프노드라고 합니다. 

이 문제는 노드의 개수 n이 주어지고, n에 해당하는 부모노드 인덱스를 입력으로 받습니다(부모 노드가 없는 경우에는 -1)

마지막으로 삭제할 노드를 입력 받고, 이러한 과정을 거친 후의 리프 노드의 개수를 구하는 문제입니다.

 

입력에서 루트노드에 대한 인덱스(입력받은 부모노드의 인덱스가 -1이면 해당 인덱스는 루트 노드의 인덱스)를 찾아주고, 깊이 우선 탐색(dfs)을 루트노드를 기점으로 진행해줘야 합니다.

 

해당 인덱스를 기점으로 인접 노드의 개수가 0, 1, (0, 1)이 아닌 경우로 구분해서 문제를 풀어줘야 합니다.

1. 인접 노드의 개수가 0개인 경우 : 해당 노드는 리프노드기 때문에, 개수를 늘려줌.
2. 인접 노드의 개수가 1개인 경우 : 만약 탐색할 노드가 삭제할 노드인지 검사 
   1. 탐색할 노드가 삭제할 노드이면 해당 노드는 리프노드가 됩니다(자식의 개수가 1인데, 해당 노드를 삭제하였기 때문)
3. 그 이외의 경우 인접한 노드를 하나씩 방문

<코드>

#include <iostream>
#include <vector>

using namespace std;
vector<int>tree[51];
int res = 0;
int delete_node;
void dfs(int start)
{
    if(start == delete_node) return;
    // 자식노드 없는경우 -> 리프노드
    if(tree[start].size()==0)
    {
        res++;
        return;
    }
    // 자식노드 하나인경우 -> 삭제된다면, 해당노드 -> 리프노드
    else if(tree[start].size()==1)
    {
        if(tree[start][0] == delete_node) 
        {
            res++;
            return;
        }
    }
    // 그렇지 않은 경우 dfs탐색
    for(auto elem : tree[start]) 
    {
        dfs(elem);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;

    int root_node;
    
    for(int i=0;i<n;i++)
    {
        int parent;
        cin>>parent;
        if(parent == -1) root_node = i;
        else tree[parent].push_back(i);
    }
    cin>>delete_node;
    dfs(root_node);
    cout<<res<<'\n';
}