# 2533. 사회망 서비스(SNS)

관련 알고리즘 : 재귀, DP

 

문제 링크 : https://www.acmicpc.net/problem/2533

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

 

---

해결 과정

 

문제를 보면, 어떤 아이디어를 SNS에서 퍼뜨리고자 할 때

• 얼리 아답터가 아닌 사람은 모든 친구가 얼리 어답터여야 아이디어를 받아들임 
• 얼리 어답터인 사람은 친구가 얼리 어답터인지 여부에 관계없이 아이디어를 받아들임

즉,

• 얼리 어답터가 X인 사람 => 연결된 친구들이 모두 얼리 어답터-----------
• 얼리 어답터가 O인 사람 => 연결된 친구가 얼리어답터 O/X 2경우로 나누어 계산, 더 작은 값

1번부터 차례로 돌며 깊이탐색 및 재귀 이용, 이후 메모이제이션을 통해 알맞은 값을 배열에 저장해준다.

 

1. dp[i][0] += dp[i_child][1] // 부모 노드가 얼리아답터가 아닐 때, 자식 노드들은 모두 얼리어답터
2. dp[i][1] = min (dp[i_child][0], dp[i_child][1]) // 부모 노드가 얼리아답터일때, 자식 노드들이 얼리어답터 O/X인 경우 중 최솟값

---

C++ 코드

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

vector<int> vec[1000001];
int dp[1000001][2]; // 얼리어답터 0, 얼리어답터x 1
bool check[1000001]; // 지난 곳 체크

void solve(int a) // 깊이탐색 & dp 이용
{
	check[a] = true;
	dp[a][1] = 1; // 얼리어답터라 가정 시, 결과값 본인 포함 1로 시작
    
	for (int i = 0; i < vec[a].size(); i++)
	{
		int child = vec[a][i];
        
		if (check[child] == false)
		{
			solve(child);		
			dp[a][0] += dp[child][1]; // 부모노드가 얼리어답터x일 때, 자식노드는 모두 얼리어답터
			dp[a][1] += min(dp[child][1], dp[child][0]); // 부모노드가 얼리어답터일때, 자식노드 2가지 경우 중 최솟값

		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    cout.tie(0);
    
	memset(check, false, sizeof(check)); // false로 초기화
    
	int N; // 트리 정점 개수
	cin >> N;
    
	for (int i = 0; i < N-1; i++)
	{
		int u, v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	solve(1); // 첫번째 노드부터 돌며 dp
	cout << min(dp[1][0], dp[1][1]); // 첫번째 노드가 얼리어답터일때와 아닐 때 중 최솟값 도출
}