백준 1068: 트리

문제 요약

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

문제 분류

• 그래프 이론
• 그래프 탐색
• 트리
• DFS

문제 풀이

DFS 혹은 BFS로 탐색하며 탐색하면서 리프노드의 개수를 찾는데, 탐색 노드가 제거할 노드와 같을 때만 제외해주면 된다.

결국 어떤 트리의 리프노드는 해당 트리의 루트노드에서 자식노드를 루트노드로 하는 서브트리의 합과 같다. 이진 트리의 경우 루프노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 루트노드의 합을 해주면 된다.

나는 DFS로 풀었는데, 자식노드를 DFS한 결과를 누적시켜서 반환해주었다. 해당 노드에 자식노드가 없다면 1을 리턴, 만약 탐색한 노드가 제외하려는 노드와 같다면 이제 달라지는데, 제외하려는 노드의 형제노드가 없다면 1을 리턴, 그렇지 않다면 0을 리턴한다. 제외하려는 노드가 부모노드의 유일한 자식노드라면 부모노드가 리프노드가 되므로 1을 리턴해야한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int n, m;
multimap<int, int> mm;

int dfs(int idx, int prev) {
	if (idx == m) {
		auto rg = mm.equal_range(prev);
		auto b = rg.first;
		b++;
		if (b == rg.second) return 1;
		return 0;
	}
	int sum = 0;
	auto rg = mm.equal_range(idx);
	
	if (rg.first == rg.second) return 1;
	for (auto& it = rg.first; it != rg.second; it++) {
		sum += dfs(it->second, idx);
	}
	return sum;
}

int main() {
	int s, in;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		mm.insert({ in, i });
		if (in == -1) s = i;
	}
	cin >> m;
	if (s == m) cout << 0;
	else cout << dfs(s, -1);
	return 0;
}