백준 1068번: 트리 (C++)

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

1068번: 트리

---

Solved By: DFS

 

DFS를 선언하면서 자신이 Leaf Node인지 아닌지를 판단할 수 있는 코드가 필요했습니다. 어떤 노드의 parent 노드는 방문이 다 된 상태이기 때문에 현재 노드에서 방문할 노드가 생기면 이는 Leaf Node로 판단하게 했습니다.

방문할 노드가 있다는 것은 Child Node가 있다는 것이고 이는 Leaf Node가 아님을 뜻하기 때문입니다.

 

그리고, Root Node가 지워버리는 노드로 선정된다면 이는 예외처리로 보고 바로 0을 출력하게 해줬습니다.

#include <iostream>
#include <vector>
#define MAX 51
using namespace std;

vector<int> adj[MAX];
int n;
int ernode;
bool visited[MAX];
int cnt = 0;

void dfs(int cur){
    visited[cur] = true;
    bool flag = true; // leaf인가 아닌가
    for(auto nxt : adj[cur]){
        if(visited[nxt]) continue;
        if(nxt == ernode) continue;
        flag = false;
        dfs(nxt);
    }
    if(flag) cnt++;
    return;
}

int main(){
    cin >> n;
    int root;
    for(int i = 0; i < n; i++){
        int v; cin >> v;
        if(v == -1){
            root = i;
        }
        else{
            adj[v].push_back(i);
        }
    }
    
    cin >> ernode;
    if(root == ernode) cout << 0;
    else{
        dfs(root); cout << cnt;
    }
    return 0;
}