[BOJ 1068] 트리_DFS (C++)

[문제]

https://www.acmicpc.net/problem/1068

트리가 주어졌을 때, 노드 하나를 지운다. 이 때 남은 트리에서 리프 노드의 개수를 구하는 문제이다. (노드를 지우면 그 노드와 그 노드의 모든 자손이 트리에서 제거된다.)

[사용 알고리즘]

DFS(깊이 우선 탐색)

[풀이 핵심]

• 트리 문제이지만 트리를 구현해서 해결하는 것보다 DFS를 통한 탐색이 더 효율적이다.
• 뿌리 노드부터 DFS를 돌며 리프 노드의 개수를 세어준다. DFS를 돌때 조건문으로 제거하려는 노드는 탐색하지 않는 식으로 해결했다. (제거하려는 노드를 탐색하지 않으면 해당 노드의 자손인 리프 노드를 세지 않기 때문)

[코드]

//boj1068번_트리_그래프

#include<iostream>

using namespace std;

bool tree[51][51];
bool visited[51];

int N;
int root;
int leaf_count = 0;

int erase_node;

void DFS(int V) {
	bool leaf = true;

	for (int i = 0; i < N; i++) {
		if (tree[V][i] && i != erase_node) {
			leaf = false;
			DFS(i);
		}
	}

	if (leaf) {
		leaf_count++;
	}

}

int main() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;

		if (num == -1) {
			root = i;
		}
		else {
			tree[num][i] = true;
		}
	}

	cin >> erase_node;

	if (root == erase_node) {
		cout << 0;
		return 0;
	}

	DFS(root);

	cout << leaf_count;

	return 0;
}