[백준] 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\]);와 같이 작성한다.

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

DFS의 시간 복잡도는 $O(V+E)$인데, 주어지는 그래프는 트리이므로 간선의 수는 $E = V - 1$이다. 주어지는 노드의 수는 $N$이므로 전체 시간 복잡도는 $O(N)$이다.

그래프 정보를 저장하는 nodes 배열과 dp 배열 모두 공간 복잡도는 $O(N)$이다. 재귀 호출에서 최악의 경우 트리가 일직선으로 배치되는 경우이고, 재귀 깊이가 $N$까지 도달할 수 있다. 따라서 재귀 호출에서 최악의 공간 복잡도는 $O(N)$이다. 따라서 전체 공간 복잡도는 $O(N)$이다.

📌 코드

#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]);
}