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

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

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

 

트리 자료구조에서 dp기법을 사용하는 문제다.

편의상 얼리어답터를 노드를 칠한다고 표현하면, 현재 노드를 칠했을 때와 칠하지 않았을 때로 나눠 탑다운 재귀방식으로 문제를 해결할 수 있다.

 

1. 부모 노드를 칠했다면 현재 노드는 칠하거나, 칠하지 않거나 두 가지 경우가 가능하다.

2. 부모 노드를 칠하지 않았다면, 현재 노드는 무조건 칠해야 한다.

3. 재귀함수는 현재 노드를 루트노드로 하는 서브트리에서 문제의 조건을 만족하기 위해 필요한 얼리어답터 수의 최소값을 리턴한다.

  이때, 부모노드가 마킹된 상태라면 자식 노드는 두 가지 상태가 모두 가능하므로, 두 가지 상태 값 중 더 작은 값을 리턴한다.

  부모노드가 마킹된 상태가 아니라면, 자식 노드를 마킹하는 경우를 리턴한다.

4. 이미 메모이제이션 되어있다면 해당 값을 리턴한다.

5. 1번에서 말한것과 같이 부모 노드를 칠한 경우 현재 노드를 칠할때, 칠하지 않을 때의 tree_dp 값을 모두 업데이트 시켜주므로 부모 노드를 칠하는 경우를 먼저 검사한다. 그렇게 함으로써 자식 노드를 칠하는 경우, 칠하지 않는 경우를 모두 메모이제이션 시켜주게 되고 이후에 수행되는 현재 노드를 칠하지 않는 경우는 동일 작업을 반복하지 않고 단순히 메모이제이션 된 값을 리턴받아 사용한다.

 

#include <iostream>
#include <vector>

#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;

int n, root = 1;
vector<int> edge[1'000'001];

//tree_dp[n][0] -> n번째 노드를 루트노드로 하는 서브트리에서 
//루트 노드가 얼리어답터가 아닌 경우 조건을 만족하는데 필요한 얼리어답터의 최소값
//tree_dp[n][1] -> n번째 노드를 루트노드로 하는 서브트리에서 
//루트 노드가 얼리어답터인 경우 조건을 만족하는데 필요한 얼리어답터의 최소값
int tree_dp[1'000'001][2];

int check_early_adapter(int cur, int prev, bool prev_marked) {
	if (cur != root && edge[cur].size() < 2)
		return tree_dp[cur][!prev_marked] = !prev_marked;

	if (!prev_marked && tree_dp[cur][1])
		return tree_dp[cur][1];

	//이전 노드가 마킹되었다면 현재 노드에서 마킹 하거나 마킹 하지 않거나 둘 다 가능
	//마킹하지 않은 경우가 갱신되어 있는 경우 이미 이전 노드가 마킹된 상태로 해당 노드에 진입한
	//이력이 있다는 뜻이므로 현재 노드를 칠했을때와 칠하지 않았을 때, 두 가지 경우 모두 메모이제이션 되어있음
	if (prev_marked && tree_dp[cur][0])
		return min(tree_dp[cur][0], tree_dp[cur][1]);

	int next;
	//현재 노드를 칠하고
	tree_dp[cur][1] = 1;
	for (int i = 0; i < edge[cur].size(); i++) {
		next = edge[cur][i];
		if (next == prev) continue;

		//자식 노드들의 서브트리를 순회하면서 색칠 필요한 최소값을 갱신해줌
		tree_dp[cur][1] += check_early_adapter(next, cur, 1);
		//이전 노드가 칠해진 상태일 경우 현재 노드를 칠하지 않는 경우를 갱신해줌
		if (prev_marked) tree_dp[cur][0] += check_early_adapter(next, cur, 0);
	}

	//두 가지 모두 메모이제이션 되어있는 경우는 prev_marked = true인 경우임
	//따라서 칠하는 경우, 칠하지 않는 경우 중 작은 값 리턴
	if (tree_dp[cur][0] && tree_dp[cur][1])
		return min(tree_dp[cur][0], tree_dp[cur][1]);
	//둘 중에 하나만 메모이제이션 되어있는 경우는 prev_marked = false인 경우임
	//이 경우는 tree_dp[cur][1]만 메모이제이션 되어있음
	else
		return max(tree_dp[cur][0], tree_dp[cur][1]);
}

void solution() {
	int node1, node2, ans;
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> node1 >> node2;
		edge[node1].push_back(node2);
		edge[node2].push_back(node1);
	}

	cout << check_early_adapter(1, 0, 1);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 77568 kb

시간: 820 ms