[백준/BOJ] 백준 2533번 : 사회망 서비스(SNS)

www.acmicpc.net/problem/2533

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

트리에서 다이나믹 프로그래밍 (트리DP?)를 이용해서 문제를 해결했다. 트리를 생성해서 루트 노드가 얼리아답터인 경우와 그렇지 않은 경우 중 트리의 얼리 아답터의 수가 더 적은 값을 출력한다. cache를 사용해 어떤 노드가 얼리아답터일때와 얼리아답터가 아닐 때 계산한 값을 저장해 중복된 계산을 피했다. 부모 노드가 얼리 아답터가 아니라면 자식 노드는 무조건 얼리아답터이지만, 부모 노드가 얼리 아답터인 경우는 자식 노드가 얼리아답터가 아닌 경우와 얼리아답터인 경우 두 가지를 모두 확인했다.

 

코드

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

int n;
vector<int> adj[1000001];
vector<int> maked(1000001, 0); //트리에 노드가 만들어졌는지 확인
int cache[1000001][2];

struct node
{
	int number;
	vector<node*> children;
};

//루트노드의 번호가 root인 트리를 만든다
node* treeMake(int root)
{
	node* ret = new node();
	ret->number = root;

	maked[root] = 1;

	for (int i = 0; i < adj[root].size(); i++)
	{
		if (maked[adj[root][i]] == 0)
		{
			ret->children.push_back(treeMake(adj[root][i]));
		}
	}

	return ret;
}

//parent 트리의 루트노드가 check인경우(1:얼리아답터 0:얼리아답터가 아닌사람) 해당 트리의 얼리 아답터의 최소 수를 반환한다
int treeCheck(node* parent, int check)
{
	int& ret = cache[parent->number][check];

	//parent트리의 루트노드가 check인경우(1:얼리아답터 0:얼리아답터가 아닌사람)를 구한적이 있을때
	if (ret != -1)
		return ret;

	//자식노드가 없을때
	if (parent->children.size() == 0)
	{
		if (check == 1)
			return 1;
		else
			return 0;
	}

	if (check == 1)
		ret = 1;
	else
		ret = 0;

	for (int i = 0; i < (parent->children).size(); i++)
	{
		//부모노드가 얼리 아답터인 경우는 자식노드가 얼리아답터가 아닌경우와 얼리아답터인 경우 두가지를 모두 확인한다
		if (check == 1)
			ret += min(treeCheck(parent->children[i], 0), treeCheck(parent->children[i], 1));
		
		//부모노드가 얼리 아답터가 아니라면 자식노드는 무조건 얼리아답터이다
		else
			ret += treeCheck(parent->children[i], 1);
	}

	return ret;
}

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

	int u, v;
	node* root;

	cin >> n;

	for (int i = 0; i < n - 1; i++)
	{
		cin >> u >> v;

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	//루트노드의 번호가 1인 트리 생성
	root = treeMake(1);

	memset(cache, -1, sizeof(cache));

	//루트노드가 얼리아답터인 경우와 그렇지 않은 경우 중 트리의 얼리 아답터의 수가 더 작은 값을 출력한다
	cout << min(treeCheck(root, 1), treeCheck(root, 0));

	return 0;
}