[백준 C++] 1068 트리 - 깊이우선탐색

1068번: 트리

---

 

문제풀이

 

DFS 알고리즘 & List 자료구조를 이용해서 풀었습니다.

각 노드 마다 부모 노드를 배열에 저장해주고, 자식 노드는 리스트로 구성해주었습니다.

그리고 삭제 노드를 입력받았을 때 해당 노드의 부모의 자식 리스트에서 제거해주고

루트노드로부터 깊이 우선 탐색을 수행하도록 구현했습니다.

---

코드

cpp

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int N, Root, Cnt;
int P[50];
list<int> C[50];

void DFS(int Node)
{
‌if (C[Node].empty())
‌{
‌‌++Cnt;
‌‌return;
‌}

‌for (const int& Child : C[Node])
‌{
‌‌DFS(Child);
‌}
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(nullptr); cout.tie(nullptr);

‌cin >> N;
‌for (int i = 0; i < N; ++i)
‌{
‌‌int Parent;
‌‌cin >> Parent;
‌‌P[i] = Parent;

‌‌if (Parent == -1)
‌‌{
‌‌‌Root = i;
‌‌‌continue;
‌‌}

‌‌C[Parent].emplace_back(i);
‌}

‌int D;
‌cin >> D;
‌if (D == Root)
‌{
‌‌cout << 0;
‌‌return 0;
‌}

‌C[P[D]].erase(find(C[P[D]].begin(), C[P[D]].end(), D));

‌DFS(Root);
‌cout << Cnt;
}