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

시작하면서

　이번 문제는 트리에서의 다이나믹 프로그래밍(Dynamic Programming & Tree) 문제이다.

BOJ 2533 - 사회망 서비스(SNS)

​

문제 이해

​ 이 문제에서는 사이클이 존재하지 않는 경우 만 고려한다고 적혀있다. 그래서 top-down으로 되어있는 트리를 떠올리고 문제를 풀면 이해가 빠르다. 여기서 주의할 점은 사이클은 없지만, 한 노드가 여러 부모를 가질 수 있다. 그렇기 때문에 visited 배열을 사용해서 한 번 방문한 곳은 다시 방문하지 않도록 해서 불필요한 연산을 줄일 수 있다.

​ 해당 문제의 핵심인 얼리 어답터가 아닌 사람들은 자신의 모든 친구들이 얼리 어답터일 때만 아이디어를 받아들인다 인데, 모든 개인이 새로운 아이디어를 수용하기 위해서는 이 조건을 다음과 같이 바꿔서 볼 수 있다.

1. 내가 얼리 어답터이면 내 친구들이 얼리 어답터인지 아닌지 상관없다.
2. 내가 얼리 어답터가 아니면 내 친구들은 전부 얼리 어답터이어야만 한다.

​ 이를 바탕으로 문제를 풀면 다음과 같다.

1. 1번 노드부터 방문하면서 로직을 시작한다.
2. 방문한 노드는 visited 배열에 기록해서 다른 부모로부터 다시 방문했을 때 중복되는 연산을 하지 않도록 한다.
3. dp 배열을 만든다. [nodeIndex][0] 는 nodeIndex가 얼리 어답터가 아닌 경우, [nodeIndex][1] 은 nodeIndex가 얼리 어답터인 경우에 하위 트리의 얼리 어답터 수를 담는다.
4. 하위 트리에 이 과정을 반복하고, 마지막에 dp 의 [0], [1]에 값을 더해준다.
5. 마지막에 최상위 노드인 dp[1][0], [1] 중에 최소값을 출력한다.

​

해결

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

void MakeEarlyAdaptorCountDP(vector<vector<int>>& friends, vector<vector<int>>& dp, vector<bool>& visited, int currentNodeIndex)
{
	visited[currentNodeIndex] = true;
	dp[currentNodeIndex][0] = 0;
	dp[currentNodeIndex][1] = 1;

	for (int i = 0; i < friends[currentNodeIndex].size(); i++)
	{
		int nextNodeIndex = friends[currentNodeIndex][i];

		if (visited[nextNodeIndex] == true)
		{
			continue;
		}

		MakeEarlyAdaptorCountDP(friends, dp, visited, nextNodeIndex);

		dp[currentNodeIndex][0] += dp[nextNodeIndex][1];
		dp[currentNodeIndex][1] += min(dp[nextNodeIndex][0], dp[nextNodeIndex][1]);
	}
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	int N;
	vector<vector<int>> friends;

	cin >> N;

	N--;

	friends.resize(N + 2);
	for (int i = 0; i < N; i++)
	{
		int u, v;

		cin >> u >> v;

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

	vector<vector<int>> dp;
	vector<bool> visited(N + 2, false);
	dp.resize(N + 2);
	for (int i = 0; i < N + 2; i++)
	{
		dp[i].assign(2, -1);
	}

	MakeEarlyAdaptorCountDP(friends, dp, visited, 1);

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

	return 0;
}