[그래프 / BOJ 1068 / C++] 트리

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

1068번: 트리

1) 인접 리스트를 통해 트리를 완성한다. 이때, root를 따로 지정해준다.
2) 리프노드를 찾는 int dfs(n) 함수를 만들어준다. 이때, dfs(n)는 return 될때 n인 노드가 리프노드라면 1을, 아니면 ret를 출력한다.
2-1) 단, n이 delete_num일 경우, 더이상 함수 진행을 하지 않는다.
2-2) 반복문을 돌때마다 ret값을 갱신해준다.
3) ret를 출력해준다. (단, root노드가 delete_num인 경우는 함수를 돌면 1이 나오기 때문에, 따로 처리해서 0으로 출력한다.)

우선 이 문제의 핵심 인접리스트를 만들고, 그 인접리스트를 dfs를 통해 리프노드를 찾는 과정을 함수로 표현해야한다.

 

인접리스트는 vector<int> arr[51]; 을 통해 만들어준다.

 

dfs를 돌릴 때는 root노드부터 시작하는 것이 편하다!

 

코드를 보면서 이해해보자.

 

우선 리프노드의 정의는, 자식노드가 없는 노드를 가리킨다.(루트노드 제외)

따라서 각 노드에 대해 자식노드가 있는 확인해주고, 만약 자식노드가 없다면 1를 리턴해준다.

만약 자식노드가 있다면, 그 자식노드에 대해 다시 dfs를 진행한다.

그리고 반복문을 돌면서 ret값을 계속 갱신하여, 반복문을 벗어날 경우 ret를 출력해준다.

 

이 모습을 그림으로 표현하면 다음과 같다.

 

 

함수가 재귀적으로 돌 때 각 리프노드의 개수를 표현하면 이렇게 된다. 따라서 최종적으로 루트노드의 ret값이 이 트리의 리프노드의 개수가 된다.

이때, root노드가 delete하는 노드가 될 경우, 함수를 돌릴 때 1이 나오므로, 이때는 결과값을 0으로 출력해줘야한다.

 

 

#include <bits/stdc++.h>

using namespace std;

int N, delete_num, tmp, res;
vector<int> arr[51];

int dfs(int here){
    int ret = 0;
    int child = 0;
    for(int there : arr[here]){
        if(there == delete_num) continue;
        ret+=dfs(there);
        child++;
    }
    
    if(child==0) {return 1;} // leaf node
    
    return ret;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int root=0;
    
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        cin >> tmp;
        if(tmp==-1) {root=i; continue;} // 루트 노드
        
        arr[tmp].push_back(i); // 인접 리스트 생성
    }
    
    cin >> delete_num;
    
    if(delete_num==root){
        cout << 0;
        return 0;
    }
    cout << dfs(root); // 루트노드부터 시작
    
    
}