[백준] 2533번: 사회망 서비스(SNS)

📌 문제

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

📌 설명

DFS로 트리를 순회하며 가능한 얼리 어답터의 수를 구하는 문제이다. 최소 얼리 어답터의 수를 구하기 위해 DP를 사용한다.

먼저 노드 연결 관계를 vector 배열 nodes에 저장한다. DFS로 순회하며 DP 배열을 초기화한다. 사용할 DP 배열은 이차원 배열이다. dp[i][j]는 i번 째 노드가 얼리 어답터(j == 1) 또는 얼리 어답터가 아닐 때(j == 0) 가능한 최소 얼리 어답터의 수이다.

현재 참조하는 노드를 node, 자식 노드를 child라고 할 때 child의 DFS 순회를 마치고 node에 대한 DP배열을 초기화한다. node가 얼리 어답터가 아닐 때 자식 노드는 무조건 얼리 어답터여야 한다. 즉, dp[node][0] += dp[child][1];이다. node가 얼리 어답터일 때 자식 노드는 무조건 얼리 어답터가 아닌 것이 아니다. 즉, 얼리 어답터끼리는 연결되어도 무방하다. 단, 자식 노드가 얼리 어답터이거나 그렇지 않은 경우 중 최소인 경우를 택해야 최적이므로 dp[node][1] += min(dp[child][0], dp[child][1]);와 같이 작성한다.

답 또한 루트 노드가 얼리 어답터이거나 그렇지 않은 경우 중 최소값을 출력한다.

📌 코드

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

using namespace std;

vector<int> nodes[1000001]; // 노드 연결 관계
int dp[1000001][2]; // dp[i][j]: i번 째 노드가 얼리 어답터가 아닐 때(j == 0) 또는 얼리 어답터일 때(j == 1) 최소 얼리 어답터

void dfs(int node, int parent) {
	dp[node][0] = 0;
	dp[node][1] = 1;

	for (int i = 0; i < nodes[node].size(); i++) {
		int child = nodes[node][i];

		if (child == parent)
			continue;

		dfs(child, node);

		dp[node][0] += dp[child][1]; // node가 얼리 어답터가 아닌 경우 자식은 무조건 얼리 어답터여야 함.
		dp[node][1] += min(dp[child][0], dp[child][1]); // node가 얼리 어답터인 경우 자식은 얼리 어답터일 수도 있고 아닐 수도 있음
	}
}

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

	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		nodes[x].push_back(y);
		nodes[y].push_back(x);
	}

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