[백준] 사회망 서비스(SNS) 2533번 C++ 풀이

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

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

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> v[1000001];
int dp[1000001][2];
bool visit[1000001];
void solve(int x)
{
	visit[x] = true;
	dp[x][1] = 1;
	for (int i = 0; i < v[x].size(); i++)
	{
		int child = v[x][i];
		if (visit[child] == false)
		{
			solve(child);		
			dp[x][0] += dp[child][1];
			dp[x][1] += min(dp[child][1], dp[child][0]);

		}
	}
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	memset(visit, false, sizeof(visit));
	int N;
	cin >> N;
	for (int i = 0; i < N-1; i++)
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	solve(1);
	cout << min(dp[1][0], dp[1][1]);
}

 

dp[정점A][0] : 정점A가 일반인일때 최소 얼리어답터의 수

dp[정점A][1] : 정점A가 얼리어답터일때 최소 얼리어답터의 수 입니다.

1번 노드에서 solve함수에 노드 1을 넣어 DFS 시작( solve(1) )을 합니다.

그러면 1번노드부터 연결된 노드를 방문하며 쭉쭉 내려가는데 아래의 순서로 코드를 작성합니다.

 

1단계 ) 방문 시 dp[방문한 노드][1] 를 1로 초기화해줍니다.

왜냐하면 자신이 얼리어답터일 경우의 최소 얼리어답터의 수를 나타내는 dp[방문한 노드][ " 1 " ] 에 자신이 얼리어 답터이므로 1로 바꿔주어야 합니다.

2단계 ) 방문한 노드의 자식 노드를 solve( 자식노드 ) 를 실행함으로써 자식 노드로 쭉쭉 타고 내려갑니다.

 

 ( 2 - 1단계 )

dp[ 노드 ] [ 0 ] 은 자신이 얼리어 답터가 아님을 나타내는데 이때 자식 노드는 반드시 얼리어 답터여야 합니다.

얼리어 답터가 아니라면 아이디어가 전파가 되지 않습니다. 그러므로 dp[노드][0]은 += 해주어야 하는데

dp[노드의자식][1] 을 더해주면 됩니다.

 ( 2 - 2단계 )

dp[ 노드 ] [ 1 ]은 자신이 얼리어 답터일때를 나타내는데 이때 자식은 얼리어답터이던지 아니던지 상관없이 아이디어를 전달 가능하므로 dp[ 노드 ] [ 1 ] 에 +=을 해줄 것인데 dp[노드의자식][0] 과 dp[노드의자식][1] 중 그냥 최솟값을 더해주면 됩니다. 왜 최솟값이냐면 모든 아이디어를 전달해야 하는데 최소한의 얼리어답터의 수로 해야 하기 때문입니다.

 

3단계 )

최종적으로 그냥 처음 solve(1)으로 노드1부터 시작했으므로 노드1의 dp[1노드][1]엔 노드1이 얼리어답터일 때의 최솟값과

dp[노드1][0]엔 노드1이 얼리어답터가 아닐 때 만족하는 최소 얼리어답터의 최솟값이 담겨 있으므로

둘 중 더 작을 값을 출력해주면 정답입니다.