[백준]- 트리(1068번) c++

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

1068번: 트리

풀이

1.루트노드르르 찾는다.

2.벡터를 이용해서 트리를 만들어준다.

3.dfs를 이용해서 탐색을 한다

3-1. 자식 노드가 0개, 1개, 2개이상일때의 경우를 나눈다음 구현한다.

 

코드

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#define max 52
using namespace std;
vector <int> tree[max];
int visit[max]  = {0,};
int root[max];
int del;
int start;
int N,result = 0,dis = 0;
void dfs(int node){
    visit[node] = 1;
    if(node == del)
        return;
    int next_node;
    int child_size = tree[node].size();
    if(child_size == 0){
        result++;
    }
    else if(child_size == 1 && tree[node][0] == del){
        result++;
    }
    else{
        for(int i = 0;i<tree[node].size();i++){
            dfs(tree[node][i]);
        }
    }
}
int main(void){
    cin >> N;
    for(int i = 0;i<N;i++){
        int a;
        cin >> a;
        root[i] = a;
        if(a != -1){
            tree[a].push_back(i);
            //cout << a << " " << i <<"\n";
        }
        else{
            start = i;
        }
    }
    cin >> del;
    dfs(start);
    cout << result;
}