BOJ - 1068번 트리(C++)

문제 출처: https://www.acmicpc.net/problem/1068

문제 난이도

Silver 1 (solved.ac 이용)

문제 접근법

처음에는 queue를 이용해서 풀었다가 dfs를 이용했다.
어쨌든, 자식 노드를 vector 배열에 넣고 dfs로 탐색하면 된다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> node[51];
int delN;
int cnt;

void dfs(int startNode) {
	if (startNode == delN) return;
	if (node[startNode].empty()) {
		cnt++;
		return;
	}
	for (int i = 0; i < node[startNode].size(); i++) {
		if (node[startNode].size() == 1 && node[startNode][i] == delN) cnt++;
		else {
			dfs(node[startNode][i]);
		}
	}
}

int main() {
	int N;
	cin >> N;
	int ori = 0;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if (a == -1) {
			ori = i;
			continue;
		}
		node[a].push_back(i);
	}
	cin >> delN;
	dfs(ori);
	cout << cnt << "\n";
	
	return 0;
}