백준 1068 트리 풀이(c++)

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

제출 일자

2025년 2월 24일 15:55:09

문제 설명

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

 

입력

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

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

 

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

using namespace std;
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;
}

 

dfs 와 트리 구조를 이용하여 풀이