[백준,c++] 1068번 - 트리

문제

1068번: 트리

코드

#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;

vector<int>v[51];
bool visited[51];
int N, root;
int cnt;

void dfs(int start){
    if(v[start].empty()){
        cnt++;
        return;
    }
    else if(v[start].size()==1){
        if(visited[v[start].front()] == true) cnt++;
    }
    
    for(auto it: v[start]){
        if(!visited[it]){
            visited[it] = true;
            dfs(it);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    for(int i=0; i<N; i++){
        int node; cin>>node;
        if(node==-1) root = i;
        else if(node!=-1) v[node].push_back(i);
    }
    memset(visited,0,sizeof(visited));
    int remove; cin>>remove;
    
    visited[remove] = true;
    if(remove!=root) dfs(root);
    cout<<cnt;
}

풀이

그래프 탐색 문제입니다. 트리에서 특정 노드를 지운 후의 리프 노드 개수를 출력하면 되는 문제입니다.
visited 배열을 두어 제거한 노드의 경우 방문 처리를 하는 방법으로 제거하였고, 최종적으로 각 노드의 size가 0일 때의 노드의 개수를 세어주면 리프 노드의 개수가 됩니다.
다만 아래 입력과 같이 한줄 짜리 노드 가 있을 때 노드를 지울 때의 엣지 케이스를 조심해야 합니다.

4
-1 0 1 2
2

해당 케이스 같은 경우는 아래와 같이 자식 노드가 하나일 때, 그 노드가 제거되었다면 리프 노드의 개수를 카운팅 하는 식으로 예외처리했습니다.

    else if(v[start].size()==1){
        if(visited[v[start].front()] == true) cnt++;
    }