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

백준 2533

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

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

풀이 전 나의 생각

친구 관계 트리가 주어졌을 때, 최소 얼리 어답터의 수를 구해야 한다.

 

현재 선택한 친구가 얼리 어답터인 경우, 연결된 친구들은 모두 일반인이거나 얼리 어답터일 수 있다.

현재 선택한 친구가 일반인일 경우, 연결된 친구들은 모두 얼리 어답터가 되어야 한다.

 

조건

- 2 ≤ N ≤ 1,000,000

 

과정

이 문제에서 요구하는 것은 각 친구 즉, 노드들이 얼리 어답터인 상태인지, 아닌지를

확인하며 최소 얼리 어답터의 수를 구하는 것이다.

 

노드가 일반인일 경우, 연결된 자식 노드들은 모두 얼리어답터면 되지만

노드가 어답터라면 연결된 자식 노드가 어답터와 일반인, 둘 다 될 수 있기 때문에

각 상황에 맞는 최적의 값을 구해야 한다.

 

따라서 DFS로 노드의 끝까지 탐색하며 DP로 현재 노드가 얼리 어답터인지 일반인 인지 경우를

나눠서 최적의 답을 저장해나가며 풀어야 한다.

 

1. 트리 탐색을 위한 친구 관계를 저장해준다.

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

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

 

2. DFS로 친구 관계 트리를 탐색하며, 어답터와 일반인의 2가지 경우에서 나올 수 있는 결과를 모두 구한다.

void dfs(int st)
{
	visited[st] = true;
	dp[st][0] = 1;
	for (int next : link[st])
	{
		if (!visited[next])
		{
			dfs(next);
			dp[st][1] += dp[next][0];
			dp[st][0] += min(dp[next][1], dp[next][0]);
		}
	}
}

dp[st][0] = 1 -> 현재 노드가 어답터일 경우 최소 기초값 (현재 노드 추가)

 

dp[st][1] += dp[next][0]; -> 현재 노드가 어답터가 아닐 경우, 모든 자식 노드의 어답터 값을 넣어준다.

 

dp[st][0] += min(dp[next][1], dp[next][0]); -> 현재 노드가 일반인일 경우, 모든 자식 노드는 

어답터, 일반인의 2가지 경우가 가능하다. 따라서 둘 중 최소의 값을 넣어주며 최적해를 구해나간다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>> link(1000001);
bool visited[1000001];
int dp[1000001][2];

void dfs(int st)
{
	visited[st] = true;
	dp[st][0] = 1;
	for (int next : link[st])
	{
		if (!visited[next])
		{
			dfs(next);
			dp[st][1] += dp[next][0];
			dp[st][0] += min(dp[next][1], dp[next][0]);
		}
	}
}

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

	int N;
	cin >> N;

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

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

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