[ boj : 2533 ] 사회망 서비스(SNS)

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

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

해설 : 트리dp 문제라고는 하는데,,,,,전 점화식을 어떻게 세워야 될지 감이 잘 오질 않습니다 ㅠㅠㅠ 

그래서 dfs로만 풀었는데 추후에 업로드를 다시 하겠습니다.

 

트리가 주어지고 얼리 아답터의 개수를 최소화 시키면 됩니다.

어떤 한 정점이 얼리 아답터라면 그 정점에 연결되어 있는 모든 정점들은 얼리 아답터로 만들어줄 필요가 없겠죠.

곰곰이 생각해보면 "어떤 특성"을 가진 정점에 얼리 아답터로 설정하게 된다면,,,항상 '손해'를 보게 되는데 어떤 특성을 가진 정점이 될까요??

 

바로 '리프 노드'가 됩니다. 리프 노드에 얼리 아답터로 설정하게 되면 리프 노드와 붙어있는 정점(1개) 만이 얼리 아답터의 친구가 되므로 최소 1개 이상의 정점을 손해 보게 되는 것이죠.

 

따라서 리프 노드를 찾고 리프노드의 부모 노드부터 얼리 아답터로 설정해 준 후에 한칸씩 띄엄띄엄 얼리 아답터로 설정해주면 가장 최적의 답이 되겠죠.

 

#include<bits/stdc++.h>

using namespace std;

const int SIZE = (int)1e6+1;
int ans;
vector<int> v[SIZE];

bool dfs(int x, int p);

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

	int t;
	cin >> t;
	int x, y;
	for (int i = 0; i < t-1; i++) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,-1);
	cout << ans;
	return 0;
}
bool dfs(int x,int p)
{
	bool flag = false;
	for (int i = 0; i < v[x].size(); i++) {
		if (v[x][i] != p) {
			flag |=dfs(v[x][i], x);
		}
	}
	if (flag)ans++;
	return !flag;
}