사회망 서비스 / Tree DP

www.acmicpc.net/problem/2533

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

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

using namespace std;

int dp[1000001][2];
bool visited[1000001];



void dfs(vector<vector<int>>&friends, int i) {
	
	visited[i] = true;
	dp[i][0] = 0;
	dp[i][1] = 1;

	for (int j = 0; j < friends[i].size(); j++) {
		
		if (visited[friends[i][j]] == true)continue;

		dfs(friends, friends[i][j]);
		dp[i][0] += dp[friends[i][j]][1]; //내가 얼리가 아니면 내 친구들은 모두 얼리어야 한다. 
		dp[i][1] += min(dp[friends[i][j]][0], dp[friends[i][j]][1]); 
	}


}




int main() {

	int n;
	cin >> n;

	int a, b;

	vector<vector<int>>friends(n+1);

	for (int i = 0; i < n - 1; i++) {
		

		cin >> a;
		cin >> b;

		friends[a].push_back(b);
		friends[b].push_back(a);

	}

	dfs(friends,1);


	return 0;

}

 - tree dp 의 경우 dfs를 통해 리프 노드까지 접근하고 연산 후 그다음 부모노드로 가서 dp 연산을 하는데, 한번 지난 자식노드에 대해서는(이미 지나온 노드) 신경쓰지 않고 현재 노드와 그다음 인접한 노드에 대해서만 신경을 쓴다. 

 

현재 노드에서 얼리어답터이면 -> 인접한 다음노드는 얼리어답터이거나 얼리어답터가 아니다. 

현재 노드가 얼리어답터가 아니라면 -> 인접한 다음 노드는 얼리어답터이다.