백준/2533번/사회망 서비스(SNS)/골드3

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

문제 설명

Site: Baekjoon
Number: 2533
Category: Dynamic Programming
Rank: Gold 3

주어진 트리에서, 자신과 연결된 모든 노드가 얼리어답터인 경우 자신도 얼리어답터가 되는 조건에서 모든 노드가 얼리어답터가 되기 위한 최소 얼리어답터의 수를 구하는 문제입니다.

문제 풀이

노드의 최대 갯수가 백만이기 때문에 이중 for문으로 해결한다면 시간초과가 발생합니다. dp를 적용하여 각 노드마다 얼리어답터인 경우와 일반인인 경우를 나누어 최솟값을 구할 수 있습니다.

모든 노드를 dfs로 순회하며 다음과 같은 점화식을 적용하면 됩니다.

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

해당 노드가 1인 경우, 즉 얼리어답터인 경우 다른 연결된 노드는 얼리어답터일 필요가 없기 때문에 dp[child][0]을 가져와 더하며

노드가 0인 경우, 얼리어답터거나 아닐 수도 있기 때문에 둘 중 최솟값을 가져와 비교하여 더합니다.

#include <iostream>
#include <vector>

using namespace std;

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

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

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

		if (visited[child])
			continue;

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

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

	int N;
	cin >> N;

	vector<vector<int>> edges(N + 1, vector<int>());

	for(int i = 0; i < N-1; i++)
	{
		int par, child;
		cin >> par >> child;

		edges[par].push_back(child);
		edges[child].push_back(par);
	}

	dfs(1, edges);

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

	return 0;
}