백준 2533 사회망 서비스(SNS) (C++)

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

트리와 dp를 이용한 문제이다. 먼저 트리의 간선을 입력받으면서 벡터에 양방향으로 저장을 해준다. 그 후 아무 값에서 시작하여 트리를 모두 접근을 하면서 dp에 값을 저장해준다. dp는 각 노드마다 두개의 배열을 가지게 되는데 0은 해당 노드가 얼리어답터일 경우의 해당 노드와 자식 노드의 얼리어답터 수이고, 1은 해당 노드가 일반인일 경우 자식 노드는 무조건 얼리어답터이어야 하므로 모든 자식 노드의 개수를 나타낸다. 0일 경우 자식 노드가 일반인과 얼리어답터 중 어느 것이 더 값이 작은지 알 수 없으므로 둘 중 작은 값을 찾아 더해주었다. 모든 트리 노드를 접근해준 후 처음 시작한 노드의 dp 중 작은 값을 출력해주었다.
생각보다 어려웠던 문제였다. 트리를 접근하면서 dp를 사용한다는 생각을 떠올리지 못해 다른 사람의 코드를 참고하여 문제를 풀었다. 트리의 이러한 방식 풀이도 있다는 점을 인지해두어야 겠다.

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

using namespace std;

int N;
vector<int> tree[1000001];
bool check[1000001];
int dp[1000001][2];

void findResult(int node) {
	dp[node][0] = 1;

	for (int i = 0; i < tree[node].size(); i++) {
		int child = tree[node][i];

		if (check[child]) continue;

		check[child] = true;
		findResult(child);

		dp[node][1] += dp[child][0];
		dp[node][0] += min(dp[child][0], dp[child][1]);
	}
}

void solution() {
	check[1] = true;
	findResult(1);

	cout << min(dp[1][0], dp[1][1]);
}

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

	cin >> N;

	int u, v;
	for (int i = 0; i < N - 1; i++) {
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	solution();
	
	return 0;
}