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

문제

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

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

얼리 아답터가 아닌 사람은 자신의 친구가 모두 얼리 아답터인 경우에 아이디어가 전파되는 상황에서 얼리 아답터의 최소 수를 구하는 문제였다.

 

문제 풀이

처음에 u - v의 관계가 항상 u가 부모, v가 자식이라고 생각하고 단방향 그래프를 만들어 풀었는데 그게 아닐수도 있었다. 처음의 풀이는 루트 노드를 찾은 다음 레벨 별 순회를 하며 해당 서브트리의 dp를 갱신해줬다. 하지만 무방향 그래프였기 때문에 해당 풀이로는 이 문제를 해결할 수 없었다.

 

무방향 그래프로 변경하고, visit를 이용해 후위순회를 하게 하면서 dp를 갱신해줬고 문제를 해결할 수 있었다.

 

dp의 점화식은 다음과 같다.

dp[n][0] = 모든 child의 dp[child][1] 합
dp[n][1] = 모든 child의 min(dp[child][0], dp[child[1])의 합

 

#define MAX_INT 10000000
using namespace std;

int N;
vector<vector<int>> G;
vector<vector<int>> dp;
vector<bool> visit;


int dfs(int n) { //후위순회 하면서 dp 갱신
	visit[n] = true;

	int newDp0 = 0, newDp1 = 1;
	for (int i = 0; i < G[n].size(); i++) {
		int nextNode = G[n][i];		

		if (!visit[nextNode]) {
			dfs(nextNode);
			newDp0 += dp[nextNode][1];
			newDp1 += min(dp[nextNode][0], dp[nextNode][1]);
		}

		
	}
	dp[n][0] = min(dp[n][0], newDp0);
	dp[n][1] = min(dp[n][1], newDp1);
	return min(dp[n][0], dp[n][1]);
}

int main() {
	
	int a, b;

	scanf("%d", &N);
	
	G = vector<vector<int>>(N + 1, vector<int>());
	dp = vector<vector<int>>(N + 1, vector<int>(2, MAX_INT));
	visit = vector<bool>(N + 1, false);

	for (int i = 0; i < N-1; i++) {
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}

	int answer = dfs(1);

	printf("%d", answer);

	return 0;
}

/*
*/