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

1068번: 트리

---

 

문제풀이

 

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

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

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

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

---

코드

#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;
}