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

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다.

 

트리의 정점 개수는 최대 100만이므로 O(N log N) 이하 알고리즘을 만들어야 한다.

 

먼저 각 상태를 정의했다.

어떤 한 노드를 골랐을 때, 그 노드가 얼리 어답터인 경우에는 주변부의 얼리 어답터 여부는 중요하지 않다.

그러나 그 노드가 얼리 어답터가 아닐 경우에는 반드시 주변부 모두가 얼리 어답터야 한다.

 

이를 점화식으로 정의할 수 있었는데, 다음과 같다.

dp[i][0] : 내가 얼리 어답터가 아님 -> sum(dp[next][1])

dp[i][1] : 내가 얼리 어답터임 -> sum(min(dp[next][0], dp[next][1]))

 

이 둘을 정의한 순간 문제는 거의 풀린다. 최악의 경우에도 100만 * 2 배열을 모두 채우면 되므로 1초 안에 충분히 풀 수 있다.

 

입력이 트리이므로, 임의의 노드 1번을 루트로 잡고 위 연산을 수행해주면 문제가 해결된다.

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

#define MAX 1000000

vector<int> edges[MAX + 1];
int dp[MAX + 1][2];
int N;
bool visited[MAX + 1];

void solve(int here) {
	visited[here] = true;

	dp[here][1] = 1;
	for (int next : edges[here]) {
		if (visited[next]) {
			continue;
		}

		solve(next);
		dp[here][0] += dp[next][1];
		dp[here][1] += min(dp[next][0], dp[next][1]);
	}
}

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

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

	input();
	solve(1);
	cout << min(dp[1][0], dp[1][1]) << '\n';

	return 0;
}