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

1. 문제

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

 

2. 알고리즘 분류

• 다이나믹 프로그래밍
• 트리
• 트리에서의 다이나믹 프로그래밍

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_N 1000006

using namespace std;

int N;
vector<int> graph[MAX_N];
int dp[MAX_N][2]; // dp[x][y] = x번 노드가 0(얼리 아답터) 또는 1(일반인) 경우,
bool visited[MAX_N];

void dfs(int cur)
{
	visited[cur] = true;
	dp[cur][0] = 1;	// 얼리 아답터인 경우 1
	
    // 1. 현재 노드가 0(얼리 아답터)인 경우, dp[현재 노드][얼리 아답터] += min(dp[다음 탐색 노드][얼리 아답터], dp[다음 탐색 노드][일반인])
    // 2. 현재 노드가 1(일반인)인 경우, dp[현재 노드][일반인] += dp[다음 탐색 노드][얼리 아답터]
	for (int i = 0; i < graph[cur].size(); i++) {
		int next = graph[cur][i];
		if (visited[next]) continue;

		dfs(next);
		dp[cur][1] += dp[next][0];	// 현재 노드가 1(일반인)인 경우, 다음 탐색 노드의 0(얼리 아답터)일 때의 값 더하기
		dp[cur][0] += min(dp[next][1], dp[next][0]); // 현재 노드가 0(얼리 아답터)인 경우, min(다음 탐색 노드가 1(일반인)일 떄의 경우, 다음 탐색 노드가 0(얼리 아답터)인 경우) 더하기
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 정점 개수
	cin >> N;

	// 그래프 입력
	for (int i = 0; i < N; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// 1번부터 탐색
	dfs(1);

	// 1번이 얼리 아답터인 경우와 일반인인 경우, 총 2개의 경우 중에서 작은 값 출력
	cout << min(dp[1][0], dp[1][1]);

	return 0;
}

 

4. 유용한 알고리즘

 1) DFS(깊이 우선 탐색) 알고리즘

1. 정의
 - 시작 노드에서 자식 노드들을 순서대로 탐색하면서 깊이를 우선 탐색
 
2. 활용
 - 모든 노드 탐색할 때 사용하는 알고리즘

 

 2) DP(다이나믹 프로그래밍)

1. 정의
 - 점화식 풀이 과정 중 하나
 - 초항에서 천천히 기록해나가면서 풀어나가는 방법

2. 활용
 - 점화식 활용 문제