[백준 1068] 알고리즘 126일차 : 트리

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

1068번: 트리

C++ 트리

트리에서 어느 한 노드를 루트노드로하는 서브트리를 모두 삭제할때

리프노드 개수를 구하는 문제

 

접근방법

벡터로 인접리스트를 구현하고, 부모노드 정보를 담고 있는 1차원 배열을 생성한다.

인접리스트를 탐색하면서 기존 트리에서의 리프노드 개수를 카운팅한다.

지울 노드를 큐에 넣고 그 하위의 노드들도 큐에 넣어 삭제해주면서 지우는 노드가 리프노드인 경우
기존 리프노드 개수 - 1 한다.

이때 처음 지우는 노드의 부모노드가 자식을 지울노드 하나만 갖고 있다면
노드를 삭제하고 난 후 리프노드가 하나 더 생기는 셈이기 때문에 리프노드 개수 + 1 해줘야한다.
이때문에 부모노드 정보를 담고 있는 배열이 필요했다.

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main(){
    //init & input
    int n;
    cin >> n;
    
    vector<vector<int>> adj(n);
    int parent[n];
    int leaf = 0;
    
    int node;
    for(int i = 0 ; i < n ; i++){
        cin >> node;
        parent[i] = node;
        if(node != -1){
            adj[node].push_back(i);
        }
    }

    int remove;
    cin >> remove;
    
    //process
    for(int i = 0 ; i < n ; i++){
        if(adj[i].empty())
            leaf++;
    }
    
    queue<int> q;
    q.push(remove);
    if(parent[remove] != -1 && adj[parent[remove]].size() == 1){
        leaf++;
    }
    
    while(!q.empty()){
        int parent = q.front();
        q.pop();
        if(adj[parent].empty()){
            leaf--;
        }
        for(int i = 0 ; i < adj[parent].size() ; i++){
            q.push(adj[parent][i]);
        }
    }
    
    //output
    cout << leaf;
    
    return 0;
}