[백준]/C++

백준 1068번 트리 [C++]

경우42 2023. 9. 18. 09:13
반응형

 

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

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

 

 

#전체 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> tree[51];
int check[51];
int leaf = 0;
int wither;
int root;

void findLeaf(int node ) {
    check[node] = true;
    
    if (node == wither) return;

    bool isLeaf = true;

    for (int i = 0; i < tree[node].size(); i++) {
        int nextNode = tree[node][i];
        if (check[nextNode] != true && nextNode != wither) {
            isLeaf = false;
            findLeaf(nextNode);
        }
    }

    if (isLeaf) leaf++;

}


int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;     cin >> n;

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

    }
    cin >> wither;
    
    findLeaf(root);

    cout << leaf << "\n";


    return 0;
}

 

벡터로 트리를 구현했다.

리프는 dfs를 사용해서 찾았다

반응형