[백준] 2533 - 사회망 서비스(SNS)

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

2533번: 사회망 서비스(SNS)

 

이 문제를 풀고 나서 분류가 트리 dp에 있다는 것을 알았다.

하지만 본인은 dfs로만 풀었다.

 

본인이 해결방법은 다음과 같다.

dfs를 돌리면서 해당 노드의 하위 노드가 얼리어답터가 아니면(ret = false), 무조건 해당 노드는 얼리어답터이어야 하므로 그때 ans을 1 증가시켰다.

 

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

int n;
vector<vector<int>> v;
int visit[1000001];
int ans;
bool go(int node) {
	
	bool ret = 0;
	visit[node] = 1;

	for (auto& i : v[node]) {
		if (!visit[i]) {
			if (!go(i)) {
				ret = true;
			}
		}
	}
	if (ret)ans++;
	return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	cin >> n;
	v.resize(n + 1);
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	go(1);
	cout << ans;
}