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

문제 요약

트리에서 각 정점들이 최소 1개 이상의 얼리 어답터인 정점과 인접하게 해야할 경우, 최소의 얼리 어답터 정점의 수를 구하시오.

문제 분류

• 다이나믹 프로그래밍
• 트리
• 트리에서의 다이나믹 프로그래밍

문제 풀이

트리의 어느 정점을 최소의 얼리 어답터로 지정하는 문제이다. 이때 어느 부분 트리에서 최소의 얼리 어답터 수는 정해지기 때문에 DP로 풀 수 있다.

만약 현재 탐색하는 정점이 얼리 어답터인 경우, 다음 노드는 얼리 어답터이거나, 얼리 어답터가 아니어도 된다. 따라서 다음 정점이 얼리 어답터인 경우와 아닌경우로 나누어 그 최소값의 합을 구하면 된다. 또한, 현재 정점이 얼리 어답터이므로 반환할 DP값에 1을 더해준다.

반대로 현재 탐색하는 정점이 얼리 어답터가 아닌 경우, 다음 방문하는 정점은 모두 얼리 어답터여야 한다. 즉, 다음으로 탐색하는 모든 정점들을 얼리 어답터로 만들어서 그 합을 반환하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int n, dp[1000000][2];
multimap<int, int> mm;
bool visited[1000000];

int dfs(int idx, int d) {
	if (dp[idx][d] > 0) return dp[idx][d];
	visited[idx] = true;
	auto rg = mm.equal_range(idx);
	if (d) {
		for (auto& it = rg.first; it != rg.second; it++) {
			if (!visited[it->second])
				dp[idx][d] += min(dfs(it->second, 0), dfs(it->second, 1));
		}
		dp[idx][d]++;
	}
	else {
		for (auto& it = rg.first; it != rg.second; it++) {
			if (!visited[it->second])
				dp[idx][d] += dfs(it->second, 1);
		}
	}
	visited[idx] = false;
	return dp[idx][d];
}

int main() {
	int u, v;
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d%d", &u, &v);
		mm.insert({ u - 1,v - 1 });
		mm.insert({ v - 1,u - 1 });
	}
	cout << min(dfs(0, 0), dfs(0, 1));
	return 0;
}