[백준 1068] 트리 (C++)

문제

백준 1068

1068번: 트리

풀이

전형적인 트리 - dfs 문제입니다.

부모가 없는 노드(입력이 -1)를 루트 노드라고 하고, 루트 노드부터 dfs를 진행합니다.

이 때 제거하는 노드 처리가 중요한데, 루트 노드를 제거하였을 때는 0을 바로 출력해줍니다.

그 이외일 때는 제거한 노드를 기억하여, dfs를 실행할 때 방문하지 않습니다.

리프 노드는 자식이 없는 노드이므로 vector의 사이즈를 확인하여, 0이면 cnt를 ++해줍니다.

또한 제거된 노드 하나만을 자식으로 가지는 노드 또한 리프 노드입니다. 여기서 처리를 이상하게 해줬더니 처음에 틀렸습니다.

소스 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include<iostream> #include<vector> using namespace std;   vector<int> v[50]; int N; int cnt; int dnode; bool visited[50]; void dfs(int curnode) {     if (visited[curnode])         return;     visited[curnode] = true;     if (v[curnode].size() == 0 || (v[curnode].size() == 1 && v[curnode][0] == dnode))     {         cnt++;     }              for (int i = 0; i < v[curnode].size(); i++)     {         if(v[curnode][i] != dnode)             dfs(v[curnode][i]);     } }   int main() {     int rootidx = -1;     cin >> N;     for (int i = 0; i < N; i++)     {         int pa;         cin >> pa;         if (pa == -1)             rootidx = i;         else         {             v[pa].push_back(i);         }     }     cin >> dnode;     if (dnode == rootidx)     {         cout << 0;         return 0;     }     dfs(rootidx);     cout << cnt;     return 0; } Colored by Color Scripter

cs