[c++] 백준 1068, 트리

백준 1068

🌲 문제 요약

주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 남은 리프 노드의 개수를 출력하는 문제.

🌲 문제 풀이

벡터 adj에 트리의 정보를 저장한 뒤, dfs 함수를 호출하여 노드를 삭제한 이후 남아있는 리프 노드의 개수를 구한다.
adj를 root부터 순회하며 리프 노드의 개수를 구해나간다. 이때 만약 현재 탐색하는 노드가 삭제해야 하는 노드라면, continue하여 해당 노드 방향을 연산에서 제외한다.

🌲 주의

노드의 부모로 -1을 입력받는 경우에는, adj[-1]에 값을 저장하지 않도록 주의한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int n, r, root;
vector<int> adj[55];

int dfs(int here) {
	int ret = 0;
	int child = 0;
	for (int there : adj[here]) {
		if (there == r) continue;
		ret += dfs(there);
		child++;
	}
	if (child == 0) return 1;
	else return ret;
}

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