[BOJ 1068 // C++] 트리

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1068번 문제인 트리이다.
문제는 아래 링크를 확인하자.

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

1068번: 트리

이 문제에서는 주어진 rooted tree에서 어떤 한 노드와 그 노드를 루트로 하는 subtree를 삭제할 때 남는 트리의 리프노드의 개수를 세는 문제이다.

 

글쓴이는 입력을 받으면서 루트노드를 찾고 (남은) 트리를 탐색하면서 각 노드의 (삭제된 subtree의 루트노드가 아닌) 자식 노드의 개수를 세면서 개수가 0이면 답에 1을 더하는 방식으로 문제를 해결하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> G[51];
int ans = 0;
int deleted;

void dfs(int current, int parent) {
	int childcnt = 0;
	for (auto node : G[current]) {
		if (node == parent || node == deleted) continue;
		childcnt++;
		dfs(node, current);
	}
	if (childcnt == 0) ans++;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int root;
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x == -1) {
			root = i;
			continue;
		}
		G[i].push_back(x);
		G[x].push_back(i);
	}

	cin >> deleted;

	if (deleted == root) cout << 0;
	else {
		dfs(root, -1);
		cout << ans;
	}
}