[BOJ/백준][Gold5] 1068 : 트리 (C++)

 

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

1068번: 트리

[난이도] Gold5
[유형] 그래프

[풀이]
vector를 이용해 인접리스트를 만든 후 root에서부터 dfs로 순회를 해준다.
현재 노드가 삭제된 노드이면 0을 return하고, child가 empty이면 1을 return해준다.
예외처리 해주어야할 부분은 어떤 노드 n의 자식이 1개인데 이 노드가 삭제된 노드인 경우 n도 leaf 노드로 바꿔주어야 한다.

 

#include <cstdio>
#include <vector>
using namespace std;
int N,root,del;
vector<int> child[50];
int trvs(int n){
    if(n==del) return 0;
    if(child[n].empty()) return 1;
    int ret=0;
    bool f = 0;
    for(auto c : child[n]) {
        if(c==del) f=1;
        else ret+=trvs(c);
    }
    if(f && ret==0) return 1;
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int par;
        scanf("%d",&par);
        if(par!=-1) child[par].push_back(i);
        else root=i;
    }
    scanf("%d",&del);   
    printf("%d",trvs(root));
} 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1068.cpp