[백준 BOJ][C++]1068번 트리 풀이: DFS

 

 

 

 

 이 문제는 DFS로 해결할 수 있습니다. 

 

 아이디어는 간단합니다.

 

 탐색 과정에서 자식 노드 중 혹은 자기 자신이 삭제할 노드 dnode라면 그 방향으로의 탐색은 하지 않으면 됩니다.

 

 리프 노드는 자식 노드가 없는 노드이므로, 자식 노드가 있다는 것을 나타낼 flag가 false라면 리프 노드라는 의미이므로 그때 리프 노드의 개수 leaf를 증가 시킵니다. 

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>

using namespace std;

int n;
int tree[50][50];
int dnode;
int leaf;

void dfs(int node) {

	if (node == dnode)
		return;

	bool flag = false;

	for (int i = 0; i < n; i++) {
		if (i != dnode && tree[node][i] == 1) {
			if (!flag)
				flag = true;

			dfs(i);
		}
	}

	if (!flag)
		leaf++;
}

int main(void) {

	int root = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int parent;
		cin >> parent;

		if (parent == -1) {
			root = i;
			continue;
		}

		tree[parent][i] = 1;
	}

	cin >> dnode;

	dfs(root);

	cout << leaf;

	return 0;
}