백준 1068 트리 (C++)

1068번: 트리

dfs를 이용한 문제이다. 처음 입력받을 때 vector를 활용해 부모 노드에 자식 노드를 차례대로 저장해주었다. 그 후 dfs를 통해 지워지는 노드인 M과 자식 노드들을 제거해주고 자식 노드로 M을 가지는 노드를 찾아 제거해주었다. 자식 노드가 없는 리프 노드의 수를 카운트해 출력해주었다.
처음에는 위상 정렬을 이용해서 문제를 풀려고 했는데 굳이 위상 정렬을 사용하지 않아도 더 간단히 풀 수 있다고 판단해 dfs로 풀게 되었다. 오타때문에 시간이 좀 오래 걸렸다. 오타를 주의하자.

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

using namespace std;

int N, M, res = 0;
vector<int> v[50];
bool check[50];

void dfs(int m) {
	check[m] = true;

	for (int i = v[m].size() - 1; i >= 0; i--) {
		dfs(v[m][i]);

		v[m].pop_back();
	}
}

void solution() {
	dfs(M);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < v[i].size(); j++) {
			if (v[i][j] == M) {
				v[i].pop_back();
			}
		}
		if (!check[i] && v[i].size() == 0) {
			res++;
		}
	}

	cout << res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		
		if (a == -1) continue;

		v[a].push_back(i);
	}

	cin >> M;

	solution();
	
	return 0;
}